题目描述
一棵树上有n个节点，编号分别为1到n，每个节点都有一个权值w。
我们将以下面的形式来要求你对这棵树完成一些操作：
I. CHANGE u t : 把结点u的权值改为t
II. QMAX u v: 询问从点u到点v的路径上的节点的最大权值
III. QSUM u v: 询问从点u到点v的路径上的节点的权值和
注意：从点u到点v的路径上的节点包括u和v本身
输入输出格式
输入格式：
输入文件的第一行为一个整数n，表示节点的个数。
接下来n – 1行，每行2个整数a和b，表示节点a和节点b之间有一条边相连。
接下来一行n个整数，第i个整数wi表示节点i的权值。
接下来1行，为一个整数q，表示操作的总数。
接下来q行，每行一个操作，以“CHANGE u t”或者“QMAX u v”或者“QSUM u v”的形式给出。
输出格式：
对于每个“QMAX”或者“QSUM”的操作，每行输出一个整数表示要求输出的结果。
输入输出样例
输入样例#1： 复制
4 1 2 2 3 4 1 4 2 1 3 12 QMAX 3 4 QMAX 3 3 QMAX 3 2 QMAX 2 3 QSUM 3 4 QSUM 2 1 CHANGE 1 5 QMAX 3 4 CHANGE 3 6 QMAX 3 4 QMAX 2 4 QSUM 3 4
输出样例#1： 复制
4 1 2 2 10 6 5 6 5 16
说明
对于100％的数据，保证1<=n<=30000，0<=q<=200000；中途操作中保证每个节点的权值w在-30000到30000之间。
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> using namespace std; const int N=3e4+5; const int INF=599518803; int n,m; int opt,x,y; int w[N],bound; int head[N],num_edge; struct Edge { int v,nxt; }edge[N<<1]; struct Node { int fa,son; int top; int dep; int size; int s,t; }node[N]; struct TREE { TREE *lson,*rson; int l,r,mid; int sum,maxn; }tree[N<<2]; typedef TREE* Tree; Tree now_node=tree,Root; inline int read() { char c=getchar();int num=0,f=1; for(;!isdigit(c);c=getchar()) f=c=='-'?-1:f; for(;isdigit(c);c=getchar()) num=num*10+c-'0'; return num*f; } inline void add_edge(int u,int v) { edge[++num_edge].v=v; edge[num_edge].nxt=head[u]; head[u]=num_edge; } void dfs1(int u) { node[u].size=1; for(int i=head[u],v;i;i=edge[i].nxt) { v=edge[i].v; if(v==node[u].fa) continue; node[v].fa=u; node[v].dep=node[u].dep+1; dfs1(v); node[u].size+=node[v].size; if(node[v].size>node[node[u].son].size) node[u].son=v; } } void dfs2(int u,int top) { node[u].top=top; node[u].s=++bound; if(node[u].son) { dfs2(node[u].son,top); for(int i=head[u],v;i;i=edge[i].nxt) { v=edge[i].v; if(v==node[u].fa||v==node[u].son) continue; dfs2(v,v); } } node[u].t=bound; } void build(Tree &root,int l,int r) { root=++now_node; root->l=l,root->r=r,root->mid=l+r>>1; // root->maxn=-INF; if(l==r) return; build(root->lson,l,root->mid); build(root->rson,root->mid+1,r); } void update(const Tree &root,int pos,int k) { if(root->l==root->r) { root->sum=root->maxn=k; return; } if(pos<=root->mid) update(root->lson,pos,k); else update(root->rson,pos,k); root->sum=root->lson->sum+root->rson->sum; root->maxn=max(root->lson->maxn,root->rson->maxn); } int query_sum(const Tree &root,int l,int r) { if(l<=root->l&&root->r<=r) return root->sum; if(r<=root->mid) return query_sum(root->lson,l,r); else if(l>root->mid) return query_sum(root->rson,l,r); else return query_sum(root->lson,l,root->mid)+query_sum(root->rson,root->mid+1,r); } int query_max(const Tree &root,int l,int r) { if(l<=root->l&&root->r<=r) return root->maxn; if(r<=root->mid) return query_max(root->lson,l,r); else if(l>root->mid) return query_max(root->rson,l,r); else return max(query_max(root->lson,l,root->mid),query_max(root->rson,root->mid+1,r)); } int Query_sum(int x,int y) { int fx=node[x].top,fy=node[y].top; int ans=0; while(fx!=fy) { if(node[fx].dep>node[fy].dep) { ans+=query_sum(Root,node[fx].s,node[x].s); x=node[fx].fa; fx=node[x].top; } else { ans+=query_sum(Root,node[fy].s,node[y].s); y=node[fy].fa; fy=node[y].top; } } if(node[x].dep>node[y].dep) ans+=query_sum(Root,node[y].s,node[x].s); else ans+=query_sum(Root,node[x].s,node[y].s); return ans; } inline int Query_max(int x,int y) { int fx=node[x].top,fy=node[y].top; int ans=-INF; while(fx!=fy) { if(node[fx].dep>node[fy].dep) { ans=max(ans,query_max(Root,node[fx].s,node[x].s)); x=node[fx].fa; fx=node[x].top; } else { ans=max(ans,query_max(Root,node[fy].s,node[y].s)); y=node[fy].fa; fy=node[y].top; } } if(node[x].dep>node[y].dep) ans=max(ans,query_max(Root,node[y].s,node[x].s)); else ans=max(ans,query_max(Root,node[x].s,node[y].s)); return ans; } char s[10]; int main() { n=read(); for(int i=1,u,v;i<n;++i) { u=read(),v=read(); add_edge(u,v); add_edge(v,u); } for(int i=1;i<=n;++i) w[i]=read(); dfs1(1); dfs2(1,1); build(Root,1,n); for(int i=1;i<=n;++i) update(Root,node[i].s,w[i]); m=read(); while(m--) { cin>>s; // cout<<s<<endl; if(s[0]=='C') { x=read(),y=read(); update(Root,node[x].s,y); } else if(s[1]=='M') { x=read(),y=read(); printf("%d ",Query_max(x,y)); } else { x=read(),y=read(); printf("%d ",Query_sum(x,y)); } } return 0; }