一题面一棵树上有 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每个点的重孩子进行重链剖分2dfs2划分重链1得出3个新基本信息即 top每个点所在链的链头 dfn每个点的dfs序 fn每个dfs序所对应的点的编号2分链 重孩子的链头自己链头 轻孩子单开一条链3对dfs序构建线段树 dfs序通用性质把树压成一维数组同一条重链上所有节点的dfn编号是一段连续区间 可以把树上路径转成线段树区间任意两点路径能够拆成多段连续区间 所以可以使用线段树维护树上路径其中pushupbuild普通对于线段树查询的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); xfa[top[x]]; } if(depth[x]depth[y]) return x; else return y; }借助条链把 x 到 y 的树上路径拆成若干条完整重链 最后同链的一段三代码详细解析在注释#includebits/stdc.h #define ll long long using namespace std; const int N3e45; 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[N2]; vectorint g[N]; void pushup(int root) { st[root].maxxmax(st[root1].maxx,st[root1|1].maxx); st[root].sumst[root1].sumst[root1|1].sum; } void build(int root,int L,int R) { st[root].LL; st[root].RR; if(LR) { st[root].maxxst[root].suma[fn[L]];//注意对dfs序打线段树要反映射回编号 return ; } int midLR1; build(root1,L,mid); build(root1|1,mid1,R); pushup(root); } void update(int root,int L,int R,int k,int val) { if(LR) { st[root].maxxst[root].sumval; return ; } int midLR1; if(kmid) update(root1,L,mid,k,val); else update(root1|1,mid1,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(vf) 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(type1){ if(lLRr){ return st[root].maxx; } int midLR1; if(rmid) return query(root1,L,mid,l,r,type); else if(lmid) return query(root1|1,mid1,R,l,r,type); else return max(query(root1,L,mid,l,r,type),query(root1|1,mid1,R,l,r,type)); } else{ if(lLRr){ return st[root].sum; } int midLR1; if(rmid) return query(root1,L,mid,l,r,type); else if(lmid) return query(root1|1,mid1,R,l,r,type); else return query(root1,L,mid,l,r,type)query(root1|1,mid1,R,l,r,type); } } int query_chain(int x,int y,int type) { if(type1) ans-0x3f3f3f3f; else ans0; while(top[x]!top[y]) { if(depth[top[x]]depth[top[y]]) swap(x,y); int tmpquery(1,1,n,dfn[top[x]],dfn[x],type);//路径的一部分 if(type1) ansmax(ans,tmp); else anstmp; xfa[top[x]];//跳到不同的链直到共链 } if(depth[x]depth[y]) swap(x,y); int tmpquery(1,1,n,dfn[y],dfn[x],type);//对dfs序打线段树此时跳完后的x和y共链,这是最后的那部分路径 if(type1) ansmax(ans,tmp); else anstmp; return ans; } int main() { scanf(%d,n); for(int i1; in; i){ int aa,bb; scanf(%d%d,aa,bb); g[aa].push_back(bb); g[bb].push_back(aa); } for(int i1;in;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)); } } } }好久没干这活了大肘子欢迎指正
