题意：
一些点，每个点有一个权值。有三种操作：点与点连边，单点修改权值，求两点之间路径上点的权值和（需要判输入是否合法）
题解：
以前一直想不通为什么神犇们的模板中LCT在link和cut后都要在根节点打翻转标记。现在明白了，因为只有这样才能保持深度的正确性，以前没有因此炸过是因为我以前都是把LCT拿来当链剖用的，根本不用link和cut~~这道题是LCT模板题也没什么好说的。不过CCZ大爷有更快的做法，就是离线读入所有连边操作，然后建一棵树用链剖，判断输入是否合法就在线用并查集查询与维护。orzCCZ！
代码：
#include <cstdio>
#include <algorithm>
#include <cstring>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 50000
using namespace std; int fa[maxn],ch[maxn][],sm[maxn],v[maxn];bool rev[maxn];
inline void update(int x){
if(x==)return; sm[x]=v[x];
if(ch[x][])sm[x]+=sm[ch[x][]]; if(ch[x][])sm[x]+=sm[ch[x][]];
}
inline bool is_root(int x){
if(x==||fa[x]==)return ;
return x!=ch[fa[x]][]&&x!=ch[fa[x]][];
}
inline void pushdown(int x){
if(rev[x]){
swap(ch[x][],ch[x][]); if(ch[x][])rev[ch[x][]]^=; if(ch[x][])rev[ch[x][]]^=; rev[x]^=;
}
}
void rotate(int x){
if(x==||is_root(x))return;
int a1=fa[x],a2=fa[fa[x]],a3; bool b1=(x==ch[a1][]),b2=(a1==ch[a2][]),b3=is_root(a1); a3=ch[x][!b1];
if(!b3)ch[a2][b2]=x; fa[x]=a2; ch[a1][b1]=a3; if(a3)fa[a3]=a1; ch[x][!b1]=a1; fa[a1]=x;
update(a1); update(x); if(!b3)update(a2);
}
int dt[maxn],dts,y;
void splay(int x){
if(x==)return; dts=; y=x; while(! is_root(y))dt[++dts]=y,y=fa[y];
dt[++dts]=y; while(dts)pushdown(dt[dts]),dts--;
while(!is_root(x)){
if(!is_root(fa[x]))((x==ch[fa[x]][])^(fa[x]==ch[fa[fa[x]]][]))?rotate(x):rotate(fa[x]);
rotate(x);
}
}
int access(int x){
if(x==)return ; int t=;
while(x){splay(x); ch[x][]=t; update(x); if(t)fa[t]=x; t=x; x=fa[x];}
return t;
}
bool link(int x,int y){
if(x==||y==)return ; access(x); splay(x); rev[x]^=; fa[x]=y; return ;
}
int querysum(int x,int y){
if(x==||y==)return ; if(x==y)return v[x]; access(x); int a=access(y); splay(x);
if(x==a)return v[a]+sm[ch[a][]];else return sm[x]+v[a]+sm[ch[a][]];
}
void change(int x,int y){
splay(x); v[x]=y; update(x);
}
int find(int x){
access(x); splay(x); while(ch[x][])x=ch[x][]; return x;
}
int n,m; char s[];
int main(){
//freopen("test.txt","r",stdin);
scanf("%d",&n); inc(i,,n)scanf("%d",&v[i]),fa[i]=,ch[i][]=ch[i][]=rev[i]=,sm[i]=v[i]; scanf("%d",&m);
inc(i,,m){
int a,b; scanf("%s%d%d",s,&a,&b);
if(s[]=='b'){if(find(a)==find(b))puts("no");else link(a,b),puts("yes");}
if(s[]=='p')change(a,b);
if(s[]=='e')if(find(a)!=find(b))puts("impossible");else printf("%d\n",querysum(a,b));
}
return ;
}
20160420