题目描述
一棵树上有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”的操作，每行输出一个整数表示要求输出的结果。
输入输出样例
输入样例
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
输出样例
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> #define rep(i,a,b) for (i=a;i<=b;i++) using namespace std; struct Node { int val,sz,f,s,seg,top,dep; }a[30001]; int scnt,rev[30001]; struct Edge { int u,v,nx; }g[60001]; int cnt,list[30001]; struct Sect { int sum,max; }t[120001]; int sm,mx; int n,m; void Add(int u,int v) {g[++cnt].u=u;g[cnt].v=v;g[cnt].nx=list[u];list[u]=cnt;} void Dfs1(int x,int f) { a[x].f=f;a[x].dep=a[f].dep+1;a[x].sz=1; for (int i=list[x];i;i=g[i].nx) if (g[i].v!=f) { Dfs1(g[i].v,x); a[x].sz+=a[g[i].v].sz; if (a[g[i].v].sz>a[a[x].s].sz) a[x].s=g[i].v; } } void Dfs2(int x,int f) { int son=a[x].s; if (son) { a[son].seg=++scnt; rev[scnt]=son; a[son].top=a[x].top; Dfs2(son,x); } for (int i=list[x];i;i=g[i].nx) if (!a[g[i].v].top) { a[g[i].v].seg=++scnt; rev[scnt]=g[i].v; a[g[i].v].top=g[i].v; Dfs2(g[i].v,x); } } void Build(int x,int l,int r) { if (l==r) { t[x].max=t[x].sum=a[rev[l]].val; return; } int mid=l+r>>1; Build(x<<1,l,mid);Build((x<<1)+1,mid+1,r); t[x].max=max(t[x<<1].max,t[(x<<1)+1].max); t[x].sum=t[x<<1].sum+t[(x<<1)+1].sum; } void Change(int x,int l,int r,int val,int seg) { if (l>seg||seg>r) return; if (l==r&&l==seg) { t[x].max=t[x].sum=val; return; } int mid=l+r>>1; if (mid>=seg) Change(x<<1,l,mid,val,seg); if (mid+1<=seg) Change((x<<1)+1,mid+1,r,val,seg); t[x].sum=t[x<<1].sum+t[(x<<1)+1].sum; t[x].max=max(t[x<<1].max,t[(x<<1)+1].max); } void Query_In_Segment(int x,int l,int r,int ll,int rr) { if (r<ll||l>rr) return; if (ll<=l&&r<=rr) { sm+=t[x].sum; mx=max(mx,t[x].max); return; } int mid=l+r>>1; if (ll<=mid) Query_In_Segment(x<<1,l,mid,ll,rr); if (mid+1<=rr) Query_In_Segment((x<<1)+1,mid+1,r,ll,rr); } void Query_In_Tree(int x,int y) { int fx=a[x].top,fy=a[y].top; while (fx!=fy) { if (a[fx].dep<a[fy].dep) swap(x,y),swap(fx,fy); Query_In_Segment(1,1,scnt,a[fx].seg,a[x].seg); x=a[fx].f;fx=a[x].top; } if (a[x].dep>a[y].dep) swap(x,y); Query_In_Segment(1,1,scnt,a[x].seg,a[y].seg); } int main() { int i; char s[20]; scanf("%d",&n); rep(i,1,n-1) { int u,v; scanf("%d%d",&u,&v); Add(u,v);Add(v,u); } rep(i,1,n) scanf("%d",&a[i].val); Dfs1(1,0); scnt=1; a[1].seg=a[1].top=rev[1]=1; Dfs2(1,0); Build(1,1,scnt); scanf("%d",&m); rep(i,1,m) { int u,v; scanf("%s",&s); scanf("%d%d",&u,&v); if (s[0]=='C') Change(1,1,scnt,v,a[u].seg); if (s[0]=='Q') { sm=0;mx=-2147483647; Query_In_Tree(u,v); if (s[1]=='M') printf("%d\n",mx); else printf("%d\n",sm); } } }