一，题面
一棵树上有 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 本身。
对于每个QMAX或者QSUM的操作，每行输出一个整数表示要求输出的结果
二，理解
考虑线段树结合树链剖分，按照顺序梳理：
1，输入树，dfs1函数得出基本信息即 fa每个点的父节点 sz每棵子树大小 depth深度 maxson每个点的重孩子（进行重链剖分）
2，dfs2划分重链
（1）得出3个新基本信息即 top每个点所在链的链头 dfn每个点的dfs序 fn每个dfs序所对应的点的编号
（2）分链 重孩子的链头=自己链头 轻孩子单开一条链
3，对dfs序构建线段树 dfs序通用性质把树压成一维数组
同一条重链上所有节点的dfn编号是一段连续区间 可以把树上路径转成线段树区间
任意两点路径能够拆成多段连续区间 所以可以使用线段树维护树上路径
其中pushup，build，普通对于线段树查询的query和update均为模板代码
4，对于链查询的query_chain 求LCA模板代码如下 其中跳链步骤与之相同
int LCA(int x,int y) { while(top[x]!=top[y]) { if(depth[top[x]]<depth[top[y]]) swap(x,y); x=fa[top[x]]; } if(depth[x]<depth[y]) return x; else return y; }借助条链，把 x 到 y 的树上路径拆成若干条完整重链 + 最后同链的一段
三，代码
详细解析在注释
#include<bits/stdc++.h> #define ll long long using namespace std; const int N=3e4+5; int a[N],fn[N],fa[N],sz[N],depth[N],dfn[N],top[N],maxson[N],tot,ans,n,q; struct node { int L,R,maxx,sum; } st[N<<2]; vector<int > g[N]; void pushup(int root) { st[root].maxx=max(st[root<<1].maxx,st[root<<1|1].maxx); st[root].sum=st[root<<1].sum+st[root<<1|1].sum; } void build(int root,int L,int R) { st[root].L=L; st[root].R=R; if(L==R) { st[root].maxx=st[root].sum=a[fn[L]];//注意对dfs序打线段树要反映射回编号 return ; } int mid=L+R>>1; build(root<<1,L,mid); build(root<<1|1,mid+1,R); pushup(root); } void update(int root,int L,int R,int k,int val) { if(L==R) { st[root].maxx=st[root].sum=val; return ; } int mid=L+R>>1; if(k<=mid) update(root<<1,L,mid,k,val); else update(root<<1|1,mid+1,R,k,val); pushup(root); } void dfs1(int u,int f) {//作用：求重儿子、sz、depth、fa fa[u]=f,sz[u]=1,depth[u]=depth[f]+1; for(int v:g[u]) { if(v==f) continue; dfs1(v,u); sz[u]+=sz[v]; if(!maxson[u]||sz[maxson[u]]<sz[v]) { //v是否是u的重孩子 maxson[u]=v; } } } void dfs2(int u,int t){//作用划分重链 t即为此时u点对应的链头 top[u]=t; dfn[u]=++tot; fn[tot]=u;//反映射标记dfs序对应的编号 if(maxson[u]){//有重孩子优先走重孩子 dfs2(maxson[u],t);//链头不变，重孩子自动成链 for(int v:g[u]){ if(v!=maxson[u]&&v!=fa[u]){//是轻孩子+不重走 dfs2(v,v);//轻孩子单开链，链头是自己 } } } } int query(int root,int L,int R,int l,int r,int type){ if(type==1){ if(l<=L&&R<=r){ return st[root].maxx; } int mid=L+R>>1; if(r<=mid) return query(root<<1,L,mid,l,r,type); else if(l>mid) return query(root<<1|1,mid+1,R,l,r,type); else return max(query(root<<1,L,mid,l,r,type),query(root<<1|1,mid+1,R,l,r,type)); } else{ if(l<=L&&R<=r){ return st[root].sum; } int mid=L+R>>1; if(r<=mid) return query(root<<1,L,mid,l,r,type); else if(l>mid) return query(root<<1|1,mid+1,R,l,r,type); else return query(root<<1,L,mid,l,r,type)+query(root<<1|1,mid+1,R,l,r,type); } } int query_chain(int x,int y,int type) { if(type==1) ans=-0x3f3f3f3f; else ans=0; while(top[x]!=top[y]) { if(depth[top[x]]<depth[top[y]]) swap(x,y); int tmp=query(1,1,n,dfn[top[x]],dfn[x],type);//路径的一部分 if(type==1) ans=max(ans,tmp); else ans+=tmp; x=fa[top[x]];//跳到不同的链直到共链 } if(depth[x]<depth[y]) swap(x,y); int tmp=query(1,1,n,dfn[y],dfn[x],type);//对dfs序打线段树，此时跳完后的x和y共链,这是最后的那部分路径 if(type==1) ans=max(ans,tmp); else ans+=tmp; return ans; } int main() { scanf("%d",&n); for(int i=1; i<n; i++){ int aa,bb; scanf("%d%d",&aa,&bb); g[aa].push_back(bb); g[bb].push_back(aa); } for(int i=1;i<=n;i++) scanf("%d",&a[i]); dfs1(1,0); dfs2(1,1);//1的链头是自己 build(1,1,n); scanf("%d",&q); while(q--){ char op[10]; int x,y; scanf("%s%d%d",&op,&x,&y); if(op[0]=='C'){ update(1,1,n,dfn[x],y);//对dfs序打的线段树所以找的是dfn[x] } else{ if(op[1]=='M'){ printf("%d\n",query_chain(x,y,1)); } else{ printf("%d\n",query_chain(x,y,0)); } } } }好久没干这活了，大肘子欢迎指正
