#include<cstdio> #include<cstring> #include<cctype> #include<algorithm> #include<queue> using namespace std; #define rep(i,s,t) for(int i=s;i<=t;i++) #define dwn(i,s,t) for(int i=s;i>=t;i--) #define clr(x,c) memset(x,c,sizeof(x)) #define qwq(x) for(edge *o=head[x];o;o=o->next) int read(){     int x=0,f=1;char c=getchar();     while(!isdigit(c)){         if(c==‘-‘) f=-1;c=getchar();     }     while(isdigit(c)) x=x*10+c-‘0‘,c=getchar();     return x*f; } const int nmax=3e4+5; const int inf=0x7f7f7f7f; struct edge{     int to;edge *next; }; edge es[nmax<<1],*pt=es,*head[nmax]; void add(int u,int v){     pt->to=v;pt->next=head[u];head[u]=pt++;     pt->to=u;pt->next=head[v];head[v]=pt++; } int n,m,fa[nmax],c[nmax][2],sm[nmax],mx[nmax],q[nmax],w[nmax];bool vis[nmax]; void bfs(){     int l=1,r=1,x;q[r]=1;vis[1]=1;     while(l<=r){         x=q[l++];         qwq(x) if(!vis[o->to]) fa[o->to]=x,q[++r]=o->to,vis[o->to]=1;     } } bool pdrt(int x){     return c[fa[x]][0]!=x&&c[fa[x]][1]!=x; } void update(int x){     int l=c[x][0],r=c[x][1];     sm[x]=sm[l]+sm[r]+w[x];mx[x]=max(w[x],max(mx[l],mx[r])); } void rotate(int x){     int y=fa[x],z=fa[y],l=c[y][1]==x,r=l^1;     if(!pdrt(y)) if(c[z][0]==y) c[z][0]=x;else c[z][1]=x;     fa[x]=z;fa[y]=x;fa[c[x][r]]=y;     c[y][l]=c[x][r];c[x][r]=y;     update(y);update(x); } void splay(int x){ //把一个点伸展到它所在的重链的根。      int y,z;//fa[x]=y表示以x为根的splay树的父亲是y，但是y的两个儿子（c[y][0]和c[y][1]）中没有一个是x     while(!pdrt(x)){         y=fa[x];z=fa[y];         if(!pdrt(y)) if(c[y][0]==x^c[z][0]==y) rotate(x);else rotate(y);         rotate(x);     } } int access(int x){     int t=0;     while(x) splay(x),c[x][1]=t,t=x,update(x),x=fa[x];     return t;     //考虑点u，v。假设先access（u）了，那么access（lca（u,v))时lca（u,v）是原splay的根节点，     //左边的是深度比它小的点，即是lca（u,v)到根的链。 说明access的操作是正确的。  } void qsum(int u,int v){     access(u);int lca=access(v);splay(u);     if(lca==u) printf("%d\n",w[u]+sm[c[lca][1]]);     else printf("%d\n",w[lca]+sm[c[lca][1]]+sm[u]); } void qmax(int u,int v){     access(u);int lca=access(v);splay(u);     if(lca==u) printf("%d\n",max(w[u],mx[c[lca][1]]));     else printf("%d\n",max(w[lca],max(mx[c[lca][1]],mx[u]))); } int main(){     n=read();int u,v,d;mx[0]=-inf;     rep(i,1,n-1) u=read(),v=read(),add(u,v);     rep(i,1,n) sm[i]=mx[i]=w[i]=read();bfs();     m=read();char ch[11];     rep(i,1,m){         scanf("%s",ch);u=read(),v=read();         if(ch[1]==‘H‘) splay(u),w[u]=v,update(u);         else if(ch[1]==‘S‘) qsum(u,v);         else qmax(u,v);     }     return 0; } 

#include<cstdio> #include<cstring> #include<cctype> #include<algorithm> using namespace std; #define rep(i,s,t) for(int i=s;i<=t;i++) #define dwn(i,s,t) for(int i=s;i>=t;i--) #define clr(x,c) memset(x,c,sizeof(x)) #define qwq(x) for(edge *o=head[x];o;o=o->next) int read(){     int x=0,f=1;char c=getchar();     while(!isdigit(c)){         if(c==‘-‘) f=-1;c=getchar();     }     while(isdigit(c)) x=x*10+c-‘0‘,c=getchar();     return x*f; } const int nmax=1e4+5; int n,m,fa[nmax],c[nmax][2],st[nmax],rev[nmax]; bool pdrt(int x){     return c[fa[x]][0]!=x&&c[fa[x]][1]!=x; } void pushdown(int x){     if(rev[x]){         int l=c[x][0],r=c[x][1];         rev[x]^=1;rev[l]^=1;rev[r]^=1;         swap(c[x][0],c[x][1]);     } } void rotate(int x){     int y=fa[x],z=fa[y],l=c[y][1]==x,r=l^1;     if(!pdrt(y)) if(c[z][0]==y) c[z][0]=x;else c[z][1]=x;     fa[x]=z;fa[y]=x;fa[c[x][r]]=y;     c[y][l]=c[x][r];c[x][r]=y; } void splay(int x){     int top=0,y,z;st[++top]=x;     for(int i=x;!pdrt(i);i=fa[i]) st[++top]=fa[i];     dwn(i,top,1) pushdown(st[i]);     while(!pdrt(x)){         y=fa[x];z=fa[y];         if(!pdrt(y)) if(c[y][0]==x^c[z][0]==y) rotate(x);else rotate(y);         rotate(x);     } } void access(int x){     int t=0;     while(x) splay(x),c[x][1]=t,t=x,x=fa[x]; } void rever(int x){     access(x);splay(x);rev[x]^=1; } void link(int x,int y){     rever(x);fa[x]=y; } void cut(int x,int y){     rever(x);access(y);splay(y);c[y][0]=fa[x]=0; } int find(int x){     access(x);splay(x);     int y=x;while(c[y][0]) y=c[y][0];     return y; } int main(){     n=read(),m=read();int x,y;char ch[11];     rep(i,1,m){         scanf("%s",ch);x=read(),y=read();         if(ch[0]==‘C‘) link(x,y);         else if(ch[0]==‘D‘) cut(x,y);         else {             if(find(x)==find(y)) puts("Yes");             else puts("No");         }     }     return 0; }