题目链接：https://loj.ac/problem/2125 解题思路 树链剖分基础题，单点更新，更新以x为根的子树，因为以x为根的子树就是连续的序列，所以直接记录该根的最右区间，直接区间更新即可。查询x到1的权值和，就是直接树链剖分的查询即可。
//单点修改，区间查询和与最大值 #include <iostream> #include <stdio.h> #include <cstring> #include <algorithm> using namespace std; typedef long long ll; const int maxn=1e5+5; struct node { int to,next; }edge[maxn<<1];//链式前向星 int head[maxn]; int num[maxn]; int cnt,n,q; int get()//快读 { char c; int sign=1; while((c=getchar())<'0'||c>'9') if(c=='-') sign=-1; int res=c-'0'; while((c=getchar())>='0'&&c<='9') res=res*10+c-'0'; return res*sign; } void add(int x,int y) { edge[++cnt].to=y; edge[cnt].next=head[x]; head[x]=cnt; } int fa[maxn];//x在树中的父亲 int dep[maxn];//x在树中的深度 int size[maxn];//x的子树结点数(子树大小) int son[maxn];//x的重儿子,即u->son[u]是重边 int top[maxn];//x所在重路径的顶部顶点(深度最小) int seg[maxn];//x在线段树中的位置(下标) int rev[maxn];//线段树中第x位置对应的树中结点编号,rev[seg[x]]=x int low[maxn];//以x为根的子树的里的最大序号 ll Ssum; ll sum[maxn<<2];//线段树数组 ll lazy[maxn<<2];//懒标记数组 void push_up(int k)//向上更新 { sum[k]=sum[k<<1]+sum[k<<1|1]; } void push_down(int k,int l,int r)//懒标记下传 { if(!lazy[k]) return ; int mid=(l+r)>>1; sum[k<<1]+=lazy[k]*(mid-l+1); sum[k<<1|1]+=lazy[k]*(r-mid); lazy[k<<1]+=lazy[k]; lazy[k<<1|1]+=lazy[k]; lazy[k]=0; } void query(int k,int l,int r,int L,int R)//区间查询 { if(L<=l&&R>=r) { Ssum+=sum[k]; return ; } push_down(k,l,r); int mid=(l+r)>>1; if(L<=mid) query(k<<1,l,mid,L,R); if(R>mid) query(k<<1|1,mid+1,r,L,R); } void update(int k,int l,int r,int Val,int pos)//单点修改 { if(l==r) { sum[k]+=1ll*Val; return ; } int mid=(l+r)>>1; push_down(k,l,r); if(pos<=mid) update(k<<1,l,mid,Val,pos); else update(k<<1|1,mid+1,r,Val,pos); push_up(k); } void update2(int k,int l,int r,int ll,int rr,int Val)//区间修改 { if(ll<=l&&rr>=r) { sum[k]+=1ll*Val*(r-l+1); lazy[k]+=(long long)Val; return ; } int mid=(l+r)>>1; push_down(k,l,r); if(ll<=mid) update2(k<<1,l,mid,ll,rr,Val); if(rr>mid) update2(k<<1|1,mid+1,r,ll,rr,Val); push_up(k); } void dfs1(int u,int f)//第一遍dfs,算出fa[],dep[],size[],son[] { size[u]=1; fa[u]=f; dep[u]=dep[f]+1; for(int i=head[u];i;i=edge[i].next) { int v=edge[i].to; if(v==f) continue; dfs1(v,u); size[u]+=size[v];//计算size if(size[v]>size[son[u]])//求重儿子 son[u]=v; } } void dfs2(int u,int f)//第二遍dfs,算出top[],seg[],rev[] { low[u]=seg[u]; if(son[u])//先走重儿子,使重路径在线段树中的位置连续 { seg[son[u]]=++seg[0];//根无法在这里赋值,所以根要在主程序赋值 top[son[u]]=top[u];//如果(u,v)为重边,那么u和v在同一条重路径上 rev[seg[0]]=son[u]; dfs2(son[u],u); low[u]=max(low[u],low[son[u]]); } for(int i=head[u];i;i=edge[i].next) { int v=edge[i].to; if(top[v])//top[v]有值即是被遍历过 continue; seg[v]=++seg[0]; rev[seg[0]]=v; top[v]=v;//如果(u,v)是轻边,则v就是其所在重路径的顶部结点 dfs2(v,u); low[u]=max(low[u],low[v]); } } void build(int k,int l,int r)//建立线段树 { if(l==r) { sum[k]=(long long)num[rev[l]]; return ; } int mid=(l+r)>>1; build(k<<1,l,mid); build(k<<1|1,mid+1,r); push_up(k); } void ask(int x,int y)//路径询问 { int fx=top[x],fy=top[y]; while(fx!=fy) { if(dep[fx]<dep[fy])//选择深度较大的往上跳 { swap(x,y); swap(fx,fy); } query(1,1,seg[0],seg[fx],seg[x]);//重路径对应区间[seg[fx],seg[x]] x=fa[fx]; fx=top[x]; } if(dep[x]>dep[y]) swap(x,y); query(1,1,seg[0],seg[x],seg[y]); } int main() { n=get(); q=get(); for(int i=1;i<=n;++i) num[i]=get(); for(int i=1;i<n;++i) { int x,y; x=get(); y=get(); add(x,y); add(y,x); } dfs1(1,0); seg[0]=seg[1]=top[1]=rev[1]=1;//根结点所在重路径的顶部结点一定还是根结点 dfs2(1,0); build(1,1,seg[0]); int opt; while(q--) { opt=get(); int x,y,z; if(opt==1) { x=get(); y=get(); update(1,1,seg[0],y,seg[x]); } else if(opt==2) { x=get(); y=get(); //cout<<seg[x]<<" "<<low[x]<<endl; update2(1,1,seg[0],seg[x],low[x],y); } else { Ssum=0; x=get(); ask(x,1); printf("%lld\n",Ssum); } } //cout<<seg[0]<<endl; return 0; }