题目大意：询问两点是否连通（反人类的是连通输no，不联通输yes...），单点权值修改，路径和。
思路：正常的动态树，搞搞就行了。
#include#include #include const int maxn=30010;using namespace std;int n,m;char op[15];struct LCT{ int sum[maxn],fa[maxn],c[maxn][2],rev[maxn],val[maxn]; bool isroot(int x){return (c[fa[x]][0]!=x)&&(c[fa[x]][1]!=x);} int which(int x){return c[fa[x]][1]==x;} void update(int x){sum[x]=sum[c[x][0]]+sum[c[x][1]]+val[x];} void flip(int x){swap(c[x][0],c[x][1]),rev[x]^=1;} void down(int x){if (rev[x]) flip(c[x][0]),flip(c[x][1]),rev[x]=0;} void relax(int x){if (!isroot(x)) relax(fa[x]);down(x);} void rotate(int x){ int y=fa[x],z=fa[y],nx=which(x),ny=which(y); fa[c[x][!nx]]=y,c[y][nx]=c[x][!nx]; fa[x]=z;if (!isroot(y)) c[z][ny]=x; fa[y]=x,c[x][!nx]=y;update(y); } void splay(int x){ relax(x); while (!isroot(x)){ if (isroot(fa[x])) rotate(x); else if (which(x)==which(fa[x])) rotate(fa[x]),rotate(x); else rotate(x),rotate(x); } update(x); } void access(int x){for (int p=0;x;x=fa[x]) splay(x),fa[c[x][1]=p]=x,update(x),p=x;} void makeroot(int x){access(x),splay(x),flip(x);} void modify(int x,int v){val[x]=v,splay(x);} int findroot(int x){access(x),splay(x);for (;c[x][0];x=c[x][0]);return x;} void link(int a,int b){makeroot(a),fa[a]=b;} void qsum(int a,int b){ if (findroot(a)!=findroot(b)) return puts("impossible"),void(); makeroot(a),access(b),splay(b),printf("%d\n",sum[b]); } void bridge(int a,int b){ if (findroot(a)==findroot(b)) return puts("no"),void(); else link(a,b),puts("yes"); }}T;int main(){ scanf("%d",&n); for (int i=1,a;i<=n;i++) scanf("%d",&a),T.modify(i,a); scanf("%d",&m); for (int i=1,a,b;i<=m;i++){ scanf("%s%d%d",op,&a,&b); if (op[0]=='b') T.bridge(a,b); if (op[0]=='p') T.modify(a,b); if (op[0]=='e') T.qsum(a,b); } return 0;}