#include <cstdio> #include <iostream> #include <vector> #define N 30003 #define INF 2147483647 using namespace std; int n,f[N][20],dep[N],siz[N],son[N],top[N],tot,pos[N],w[N]; int Max[N*4],Sum[N*4]; vector <int> to[N]; void dfs1(int x){ siz[x]=1; int sz=to[x].size(); for(int i=0;i<sz;++i){ int y=to[x][i]; if(y==f[x][0])continue; f[y][0]=x; dep[y]=dep[x]+1; dfs1(y); siz[x]+=siz[y]; if(siz[y]>siz[son[x]])son[x]=y; } } void dfs2(int x,int root){ top[x]=root; pos[x]=++tot; if(son[x])dfs2(son[x],root); int sz=to[x].size(); for(int i=0;i<sz;++i){ int y=to[x][i]; if(y==f[x][0] || y==son[x])continue; dfs2(y,y); } } void update(int k,int l,int r,int P,int V){ if(l==r){ Max[k]=Sum[k]=V; return; } int mid=(l+r)>>1; if(P<=mid)update(k*2,l,mid,P,V); else update(k*2+1,mid+1,r,P,V); Max[k]=max(Max[k*2],Max[k*2+1]); Sum[k]=Sum[k*2]+Sum[k*2+1]; } void up(int &x,int goal){ for(int i=15;i>=0;--i) if(dep[f[x][i]]>=goal)x=f[x][i]; } int lca(int x,int y){ if(dep[x]>dep[y])up(x,dep[y]); if(dep[x]<dep[y])up(y,dep[x]); if(x==y)return x; for(int i=15;i>=0;--i) if(f[x][i]!=f[y][i])x=f[x][i],y=f[y][i]; return f[x][0]; } int getm(int k,int l,int r,int L,int R){ if(L<=l && r<=R)return Max[k]; int res=-INF,mid=(l+r)>>1; if(L<=mid)res=max(res,getm(k*2,l,mid,L,R)); if(R>mid)res=max(res,getm(k*2+1,mid+1,r,L,R)); return res; } int gets(int k,int l,int r,int L,int R){ if(L<=l && r<=R)return Sum[k]; int res=0,mid=(l+r)>>1; if(L<=mid)res+=gets(k*2,l,mid,L,R); if(R>mid)res+=gets(k*2+1,mid+1,r,L,R); return res; } int main(){ scanf("%d",&n); for(int i=1,a,b;i<n;++i){ scanf("%d%d",&a,&b); to[a].push_back(b); to[b].push_back(a); } dep[1]=1; dfs1(1); dfs2(1,1); for(int i=1;i<=15;++i) for(int j=1;j<=n;++j)f[j][i]=f[f[j][i-1]][i-1]; for(int i=1;i<=n;++i){ scanf("%d",&w[i]); update(1,1,n,pos[i],w[i]); } int q; scanf("%d",&q); while(q--){ char s[10]; int u,v,t; scanf("%s",s); if(s[1]=='H'){ scanf("%d%d",&u,&t); w[u]=t; update(1,1,n,pos[u],t); } if(s[1]=='M'){ scanf("%d%d",&u,&v); int ans=-INF,t=lca(u,v); for(int i=u;i;i=f[top[i]][0]) if(dep[t]<dep[top[i]]) ans=max(ans,getm(1,1,n,pos[top[i]],pos[i])); else{ ans=max(ans,getm(1,1,n,pos[t],pos[i])); break; } for(int i=v;i;i=f[top[i]][0]) if(dep[t]<dep[top[i]]) ans=max(ans,getm(1,1,n,pos[top[i]],pos[i])); else{ ans=max(ans,getm(1,1,n,pos[t],pos[i])); break; } printf("%d\n",ans); } if(s[1]=='S'){ scanf("%d%d",&u,&v); int ans=0,t=lca(u,v); for(int i=u;i;i=f[top[i]][0]) if(dep[t]<dep[top[i]]) ans+=gets(1,1,n,pos[top[i]],pos[i]); else{ ans+=gets(1,1,n,pos[t],pos[i]); break; } for(int i=v;i;i=f[top[i]][0]) if(dep[t]<dep[top[i]]) ans+=gets(1,1,n,pos[top[i]],pos[i]); else{ ans+=gets(1,1,n,pos[t],pos[i]); break; } printf("%d\n",ans-w[t]); } } }
- 粉丝: 0
- 资源: 1
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助