Description
一棵树上有 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 个整数 w_i? 表示节点 i 的权值。接下来 1 行，为一个整数 q，表示操作的总数。
接下来 q行，每行一个操作，以 CHANGE u t 或者 QMAX u v 或者 QSUM u v 的形式给出。
输出格式
对于每个 QMAX 或者 QSUM 的操作，每行输出一个整数表示要求输出的结果。
Solution
模板题。。。
Code
#include <cstdio> #include <cstdlib> #include <algorithm> #include <vector> using namespace std; const int N=3e4+10; vector <int> link[N]; struct node { int l,r,lc,rc,sum,ma; }f[N*2]; int fa[N],top[N],son[N],dfn[N],size[N],n,q,a,b,cnt,tot,rt,d[N],deep[N]; char s[100]; void dfs1(int u,int fat) { size[u]=1,fa[u]=fat,deep[u]=deep[fat]+1; int siz=link[u].size(); for(int i=0;i<siz;i++) { int v=link[u][i]; if(v==fa[u]) continue; dfs1(v,u),size[u]+=size[v]; if(son[u]==0 || size[son[u]]<size[v]) son[u]=v; } } void dfs2(int u) { dfn[u]=++cnt; if(son[u]) { top[son[u]]=top[u],dfs2(son[u]); int siz=link[u].size(); for(int i=0;i<siz;i++) { int v=link[u][i]; if(v==fa[u] || v==son[u]) continue; top[v]=v,dfs2(v); } } } void push_up(int g) { int lc=f[g].lc,rc=f[g].rc; if(lc==0) return ; f[g].ma=max(f[lc].ma,f[rc].ma); f[g].sum=f[lc].sum+f[rc].sum; } void build(int &g,int l,int r) { g=++tot,f[g].l=l,f[g].r=r; if(l==r) { f[g].ma=f[g].sum=d[l]; return ; } int mid=(l+r)>>1; build(f[g].lc,l,mid); build(f[g].rc,mid+1,r); push_up(g); } void change(int g,int x,int y) { if(f[g].l==f[g].r) f[g].ma=f[g].sum=y; else { int mid=(f[g].l+f[g].r)>>1; if(x<=mid) change(f[g].lc,x,y); else change(f[g].rc,x,y); push_up(g); } } int get_max(int g,int l,int r) { if(f[g].l>=l && f[g].r<=r) return f[g].ma; else { int mid=(f[g].l+f[g].r)>>1; if(r<=mid) return get_max(f[g].lc,l,r); else if(l>mid) return get_max(f[g].rc,l,r); else return max(get_max(f[g].lc,l,mid),get_max(f[g].rc,mid+1,r)); } } int get_sum(int g,int l,int r) { if(f[g].l>=l && f[g].r<=r) return f[g].sum; else { int mid=(f[g].l+f[g].r)>>1; if(r<=mid) return get_sum(f[g].lc,l,r); else if(l>mid) return get_sum(f[g].rc,l,r); else return get_sum(f[g].lc,l,mid)+get_sum(f[g].rc,mid+1,r); } } int Get_sum(int x,int y) { int ans=0; int px=top[x],py=top[y]; while(px!=py) if(deep[px]>deep[py]) { ans+=get_sum(rt,dfn[px],dfn[x]); x=fa[px],px=top[x]; } else { ans+=get_sum(rt,dfn[py],dfn[y]); y=fa[py],py=top[y]; } if(dfn[x]<dfn[y]) ans+=get_sum(rt,dfn[x],dfn[y]); else ans+=get_sum(rt,dfn[y],dfn[x]); return ans; } int Get_max(int x,int y) { int ans=-1<<30; int px=top[x],py=top[y]; while(px!=py) if(deep[px]>deep[py]) { ans=max(ans,get_max(rt,dfn[px],dfn[x])); x=fa[px],px=top[x]; } else { ans=max(ans,get_max(rt,dfn[py],dfn[y])); y=fa[py],py=top[y]; } if(dfn[x]<dfn[y]) ans=max(ans,get_max(rt,dfn[x],dfn[y])); else ans=max(ans,get_max(rt,dfn[y],dfn[x])); return ans; } int main() { scanf("%d",&n); for(int i=1;i<n;i++) { scanf("%d%d",&a,&b); link[a].push_back(b); link[b].push_back(a); } dfs1(1,0),top[1]=1,dfs2(1); for(int i=1;i<=n;i++) scanf("%d",&d[dfn[i]]); build(rt,1,cnt); scanf("%d",&q); //CHANGE u t ：把节点 u权值改为 t； //QMAX u v ：询问点 u到点 v路径上的节点的最大权值； //QSUM u v ：询问点 u到点 v路径上的节点的权值和。 while(q--) { scanf("%s",s); scanf("%d%d",&a,&b); if(s[0]==‘C‘) change(rt,dfn[a],b); else if(s[1]==‘M‘) printf("%d\n",Get_max(a,b)); else printf("%d\n",Get_sum(a,b)); } return 0; }
原文：https://www.cnblogs.com/hsez-cyx/p/12251060.html