前言：蒟蒻刚刚学会树链剖分，写一篇博客以加深理解
树链剖分：指一种对树进行划分的算法，它先通过轻重边剖分将树分为多条链，保证每个点属于且只属于一条链，然后再通过数据结构（树状数组、BST、SPLAY、线段树等）来维护每一条链。
————百度百科
树链剖分中有如下定义：
重儿子：父亲节点的儿子中以此点为根节点的子树节点数量最多的子节点
轻儿子：父亲节点的儿子中除重儿子外的节点
重边：父亲节点和重儿子连接而成的边
轻边：父亲节点和轻儿子连接而成的边
重链：重边连接而成的链
轻链：轻边连接而成的链
链头：一条链上深度最小的节点
了解了树剖的定义，回头再看题。
题目要求在树上实现四种操作：
1.将树上从x到y结点最短路径上所有节点的值都加上z
2.求树上从x到y结点最短路径上所有节点的值之和
3.将以x为根节点的子树内所有节点值都加上z
4.求以x为根节点的子树内所有节点值之和
对于一棵树，我们先进行树链剖分——
1：Dfs1()维护节点深度，父节点编号，子树节点数，如下
void Dfs1(int f,int fa,int deep){//f为当前节点，fa为当前节点的父节点，deep为当前节点的深度
depth[f]=deep;
Fa[f]=fa;
sonnum[f]=1;//初始化孩子数（包括自己）
int heavyson=-1;
for(int i=head[f];i;i=edge[i].next){
int u=edge[i].to;
if(u==fa) continue;
Dfs1(edge[i].to,f,deep+1);
sonnum[f]+=sonnum[u];//向上传递孩子数
if(sonnum[u]>heavyson) heavyson=sonnum[u],HeavySon[f]=u;
}
}
2.Dfs2()维护剖过的数节点新编号、初始值与节点所在链的顶部节点编号，如下
void Dfs2(int f,int Top){//f为当前节点，Top为当前节点所在链的顶端
newid[f]=++tot;//新编号
neww[tot]=w[f];//新编号赋初值
top[f]=Top;//维护链顶编号
if(!HeavySon[f]) return;//如果Dfs到叶子节点就return
Dfs2(HeavySon[f],Top);
for(int i=head[f];i;i=edge[i].next){
int u=edge[i].to;
if(u==Fa[f]||u==HeavySon[f]) continue;
Dfs2(u,u);
}
}
手画一棵树并推一下会发现同一条链上的节点新编号都是连续的，这样便于我们用线段树进行维护
线段树维护方式与线段树模板无异
最后贴出AC代码：
#include<bits/stdc++.h>
using namespace std;
struct Edge{
int to;
int next;
}edge[200005];
int n,m,r,p;
int cnt=0,tot=0,flag,x,y,z;
long long head[200005];
long long w[100005],depth[100005],Fa[100005],sonnum[100005];
long long HeavySon[100005],top[100005],ans[400005],tag[400005];
long long newid[100005],neww[100005];
void add(int x,int y){
edge[++cnt].to=y;
edge[cnt].next=head[x];
head[x]=cnt;
}
void Dfs1(int f,int fa,int deep){
depth[f]=deep;
Fa[f]=fa;
sonnum[f]=1;
int heavyson=-1;
for(int i=head[f];i;i=edge[i].next){
int u=edge[i].to;
if(u==fa) continue;
Dfs1(edge[i].to,f,deep+1);
sonnum[f]+=sonnum[u];
if(sonnum[u]>heavyson) heavyson=sonnum[u],HeavySon[f]=u;
}
}
void Dfs2(int f,int Top){
newid[f]=++tot;
neww[tot]=w[f];
top[f]=Top;
if(!HeavySon[f]) return;
Dfs2(HeavySon[f],Top);
for(int i=head[f];i;i=edge[i].next){
int u=edge[i].to;
if(u==Fa[f]||u==HeavySon[f]) continue;
Dfs2(u,u);
}
}
void pushup(int k){
ans[k]=ans[k<<1]+ans[k<<1|1];
ans[k]%=p;
}
void build(int k,int l,int r){
tag[k]=0;
if(l==r){
ans[k]=neww[l];
ans[k]%=p;
return;
}
int mid=(l+r)>>1;
build(k<<1,l,mid);
build(k<<1|1,mid+1,r);
pushup(k);
}
void ff(int k,int l,int r,int delta){
tag[k]=tag[k]+delta;
ans[k]=ans[k]+delta*(r-l+1);
}
void pushdown(int k,int l,int r){
int mid=(l+r)>>1;
ff(k<<1,l,mid,tag[k]);
ff(k<<1|1,mid+1,r,tag[k]);
tag[k]=0;
}
void update(int k,int l,int r,int l1,int r1,int delta){
if(l1<=l&&r<=r1){
ans[k]+=delta*(r-l+1);
tag[k]+=delta;
return;
}
pushdown(k,l,r);
int mid=(l+r)>>1;
if(l1<=mid) update(k<<1,l,mid,l1,r1,delta);
if(r1>mid) update(k<<1|1,mid+1,r,l1,r1,delta);
pushup(k);
}
int query(int k,int l,int r,int l1,int r1){
int step=0;
if(l1<=l&&r<=r1) return ans[k]%p;
pushdown(k,l,r);
int mid=(l+r)>>1;
if(l1<=mid) step+=query(k<<1,l,mid,l1,r1),step%=p;
if(r1>mid) step+=query(k<<1|1,mid+1,r,l1,r1),step%=p;
return step%p;
}
void Tag1(int x,int y,int delta){
delta%=p;
while(top[x]!=top[y]){
if(depth[top[x]]<depth[top[y]]) swap(x,y);
update(1,1,n,newid[top[x]],newid[x],delta);
x=Fa[top[x]];
}
if(depth[x]>depth[y]) swap(x,y);
update(1,1,n,newid[x],newid[y],delta);
}
int Tag2(int x,int y){
int step=0;
while(top[x]!=top[y]){
if(depth[top[x]]<depth[top[y]]) swap(x,y);
step+=query(1,1,n,newid[top[x]],newid[x]);
step%=p;
x=Fa[top[x]];
}
step+=query(1,1,n,min(newid[x],newid[y]),max(newid[x],newid[y]));
step%=p;
return step;
}
void Tag3(int x,int delta){
delta%=p;
update(1,1,n,newid[x],newid[x]+sonnum[x]-1,delta);
}
int Tag4(int x){
return query(1,1,n,newid[x],newid[x]+sonnum[x]-1);
}
int main(){
scanf("%d%d%d%d",&n,&m,&r,&p);
for(int i=1;i<=n;i++) scanf("%lld",&w[i]);
for(int i=1;i<=n-1;i++){
scanf("%d%d",&x,&y);
add(x,y);
add(y,x);
}
Dfs1(r,0,1);
Dfs2(r,r);
build(1,1,n);
for(int i=1;i<=m;i++){
scanf("%d",&flag);
if(flag==1){
scanf("%d%d%d",&x,&y,&z);
Tag1(x,y,z);
}
else if(flag==2){
scanf("%d%d",&x,&y);
printf("%lld\n",Tag2(x,y)%p);
}
else if(flag==3){
scanf("%d%d",&x,&z);
Tag3(x,z);
}
else{
scanf("%d",&x);
printf("%lld\n",Tag4(x)%p);
}
}
return 0;
}
完结撒花！
原文：https://www.cnblogs.com/WwaiForever/p/11625000.html