竟然卡了我。。。。忘记在push_down先下传父亲的信息了。。。。还有splay里for()；卡了我10min，但是双倍经验还是挺爽的，什么都不用改。
感觉做的全是模板题，太水啦，不能这么水了。。。
不过模板都敲不对，啥也做不好！！！
#include <iostream>
#include <cstdio>
#define N 300030
using namespace std;
int n,m;
struct node
{
node *fa,*ch[];
int data,sum;
bool rev;
node(int x);
bool chr() {return this==fa->ch[];}
bool isrt() {return this!=fa->ch[] && this!=fa->ch[];}
void push_up() {sum=ch[]->sum+ch[]->sum+data;}
void setc(node *x,int t) {this->ch[t]=x; x->fa=this;}
void push_down()
{
if (!isrt()) fa->push_down();
if (rev)
{
ch[]->rev^=;
ch[]->rev^=;
swap(ch[],ch[]);
rev=;
}
}
}*null=new node(),*lct[N];
node::node (int x) {fa=ch[]=ch[]=null; data=sum=x; rev=;}
inline int read()
{
char c;
int ans=,f=;
while (!isdigit(c=getchar())) {if (c=='-') f=-;}
ans=c-'';
while (isdigit(c=getchar())) ans=ans*+c-'';
return ans*f;
}
namespace LCT
{
void rotate(node *x)
{
node *r=x->fa;
if (x==null || r==null) return;
int t=x->chr();
//x->push_down();r->push_down();
if (r->isrt()) x->fa=r->fa;
else r->fa->setc(x,r->chr());
r->setc(x->ch[t^],t);
x->setc(r,!t);
x->push_up(); r->push_up();
}
void Splay(node *x)
{
x->push_down();
for (;!x->isrt();rotate(x))
if (!x->fa->isrt())
if (x->chr()==x->fa->chr()) rotate(x->fa);
else rotate(x);
x->push_up();
}
void Access(node *x)
{
node *r=null;
for (;x!=null;r=x,x=x->fa)
{
Splay(x);
x->ch[]=r;
}
}
void MakeRoot(node *x)
{
Access(x);
Splay(x);
x->rev^=;
}
void Link(node *x,node *y)
{
MakeRoot(x);
x->fa=y;
}
void Cut(node *x,node *y)
{
MakeRoot(x);
Access(y); Splay(y);
y->ch[]->fa=null; y->ch[]=null;
}
node *Find(node *x)
{
Access(x); Splay(x);
while (x->ch[]!=null) x=x->ch[];
return x;
}
void Change(node *x,int v)
{
x->push_down();
Splay(x);
x->data=v;
x->push_up();
}
int Query(node *x,node *y)
{
MakeRoot(x);
Access(y); Splay(y);
return y->sum;
}
}
using namespace LCT;
int main()
{
char s[];
int x,y;
n=read();
for (int i=;i<=n;i++) x=read(),lct[i]=new node(x);
m=read();
for (int i=;i<=m;i++)
{
scanf("%s",s); x=read(); y=read();
if (s[]=='b') if (Find(lct[x])!=Find(lct[y])) printf("yes\n"),Link(lct[x],lct[y]);
else printf("no\n");
if (s[]=='p') Change(lct[x],y);
if (s[]=='e') if (Find(lct[x])==Find(lct[y])) printf("%d\n",Query(lct[x],lct[y]));
else printf("impossible\n");
}
return ;
}
Description
给出n个结点以及每个点初始时对应的权值wi。起始时点与点之间没有连边。有3类操作： 1、bridge A B：询问结点A与结点B是否连通。如果是则输出“no”。否则输出“yes”，并且在结点A和结点B之间连一条无向边。 2、penguins A X：将结点A对应的权值wA修改为X。 3、excursion A B：如果结点A和结点B不连通，则输出“impossible”。否则输出结点A到结点B的路径上的点对应的权值的和。给出q个操作，要求在线处理所有操作。数据范围：1<=n<=30000, 1<=q<=300000, 0<=wi<=1000。
Input
第一行包含一个整数n(1<=n<=30000)，表示节点的数目。第二行包含n个整数，第i个整数表示第i个节点初始时对应的权值。第三行包含一个整数q(1<=n<=300000)，表示操作的数目。以下q行，每行包含一个操作，操作的类别见题目描述。任意时刻每个节点对应的权值都是1到1000的整数。
Output
输出所有bridge操作和excursion操作对应的输出，每个一行。
Sample Input
5
4 2 4 5 6
10
excursion 1 1
excursion 1 2
bridge 1 2
excursion 1 2
bridge 3 4
bridge 3 5
excursion 4 5
bridge 1 3
excursion 2 4
excursion 2 5
4 2 4 5 6
10
excursion 1 1
excursion 1 2
bridge 1 2
excursion 1 2
bridge 3 4
bridge 3 5
excursion 4 5
bridge 1 3
excursion 2 4
excursion 2 5
Sample Output
4
impossible
yes
6
yes
yes
15
yes
15
16
impossible
yes
6
yes
yes
15
yes
15
16