树链剖分用来解静态树上维护路径信息的问题，例如：给定一颗点带权的树，每次去修改某条路径上所有点的点权，或是求某条路径上的点权之和，当这棵树的形态为一条链时，这实际上就是一个区间修改求和的问题，可以用线段树等数据结构方便地求解。对于其他的情况，由于树的形态不变，因此树链剖分的策略是把这棵树恰当的剖分为若干条链，每一条链就对应线段树里的一段区间，此时就可以利用线段树等进行解决了。
也许对于以上的概念你读不太懂，不过没关系，先来看看几个问题：
1、将树上x号节点到y号节点的路径上每一个节点权值增加z；
2、求树从x到y结点最短路径上所有节点的值之和
这两个问题分开来看都不是很难，但是组合起来就不好办了。这时我们需要引入一种新的方法：
树链剖分！
就像概念中说的一样，当这棵树是一条链时，只需要一个线段树就可以解决了。下面我们看一看树链剖分的基本操作：
首先我们要明确几个概念（万恶的概念QWQ）：
1、重儿子：非叶节点的儿子中子节点最多的叫做该节点的重儿子。
2、轻儿子：除了重儿子剩下的儿子就是轻儿子
3、重边：连接某节点与它的重儿子的边叫重边
4、重链：一些重边组成的链叫重链。
图中标红的节点即为父节点的重儿子，标红的边即为重边。
注意：重链的端点一定是轻儿子或根节点。
在剖分的之前中要预处理计算出以下六个数组：
dep[x]:x的深度
fa[x]:x的父亲
size[x]:x的子树大小
son[x]:x的重儿子
top[x]:x所在重链的顶部节点（深度最小）
seg[x]:x在线段树中的下标（优先遍历重儿子的dfs序）
对于前4个值我们可以进行一遍dfs，对于后2个值我们可以进行第二遍dfs......
两遍dfs参考代码：
void dfs1(int node,int father)
{
fa[node]=father;
dep[node]=dep[father]+1;
size[node]=1;
int maxson=-1;
for(int i=head[node];i;i=nxt[i])
{
int go=v[i];
if(go==father)continue;
dfs1(go,node);
size[node]+=size[go];
if(size[go]>maxson)son[node]=go,maxson=size[go];
}
}
void dfs2(int node,int topfather)
{
seg[node]=++id;
top[node]=topfather;
w[id]=num[node];
if(!son[node])return;
dfs2(son[node],topfather);
for(int i=head[node];i;i=nxt[i])
{
int go=v[i];
if(go==fa[node]||go==son[node])continue;
dfs2(go,go);//轻儿子是重链的顶端.
}
}
预处理出以上6个值后，我们就可以正式开始树链剖分了。
（1）树链剖分改路径权值：
对于任意节点x,y,LCA(x,y)存在且唯一，所以它一定在某条重链上（单独一个节点也算一条重链）于是我们就可以让x，y中较深的那一个节点跳到它所在重链的端点父亲位置，直到x，y在同一条重链上，因为第二次深度优先搜索优先遍历重儿子，所以同一条重链DFS序是连续的，也就是他们对应在线段树中的下标是连续的，就转化成了一个区间修改的问题，每次跳的时候修改seg[top[x]~seg[x]的权值即可。
树链剖分改路径权值参考代码：
void Tadd(int x,int y)
{
z%=p;
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]])swap(x,y);
add(seg[top[x]],seg[x],1);
x=fa[top[x]];
}
if(dep[x]>dep[y])swap(x,y);
add(seg[x],seg[y],1);
}
（2）树链剖分改子树权值：
由于是深度优先搜索，所以同一子树的DFS序也是连续的，以x为根节点子树的大小为size[x]，所以对应的区间为seg[x]~seg[x]+size[x]-1，区间修改即可。
树链剖分改子树权值代码：
void Treeadd(int x,int z)
{
add(seg[x],seg[x]+size[x]-1,1);
}
注意：区间修改+区间求和的操作需要标记永久化或标记下传。
完整代码：
#include<iostream>
#include<cstdio>
#define N 100005
#define M 200005
#define int long long
#define mid (l+r)/2
#define lc k*2
#define rc k*2+1
using namespace std;
struct node
{
int l,r,w,tag;
}tree[4*N];
int v[M],head[M],nxt[M],cnt;//邻接表
int n,m,r,p;//树的结点个数、操作个数、根节点序号和取模数
int q,x,y,z,num[N],w[N];
int dep[N],fa[N],size[N],son[N],top[N],seg[N],id;
//dep[x] x的深度
//fa[x] x的父亲
//size[x] x的子树大小
//son[x] x的重儿子
//top[x] x所在重链的顶部节点（深度最小）
//seg[x] x在线段树中的下标
int read()
{
int x=0,f=1;char ch=getchar();
while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}
while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-48;ch=getchar();}
return x*f;
}
void add(int a,int b)
{
v[++cnt]=b;
nxt[cnt]=head[a];
head[a]=cnt;
}
//-------------以上为基础操作以及定义-----------------
//-------------以下为线段树---------------------------
void build(int l,int r,int k)
{
tree[k].l=l;tree[k].r=r;
if(l==r)
{
tree[k].w=w[l]%p;
return;
}
build(l,mid,lc);
build(mid+1,r,rc);
tree[k].w=(tree[lc].w+tree[rc].w)%p;
}
int query(int x,int y,int k)
{
int l=tree[k].l,r=tree[k].r;
if(l>=x&&r<=y)
{
return (tree[k].w+tree[k].tag*(r-l+1))%p;
}
int res=tree[k].tag*(min(r,y)-max(l,x)+1);
if(x<=mid)res+=query(x,y,lc),res%=p;
if(y>mid)res+=query(x,y,rc),res%=p;
return res%p;
}
void add(int x,int y,int k)
{
int l=tree[k].l,r=tree[k].r;
if(l>=x&&r<=y)
{
tree[k].tag+=z;
return;
}
tree[k].w+=(min(r,y)-max(l,x)+1)*z;
if(x<=mid)add(x,y,lc);
if(y>mid)add(x,y,rc);
}
//---------------以上为线段树------------------
//---------------以下为树链剖分----------------
void Tadd(int x,int y)
{
z%=p;
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]])swap(x,y);
add(seg[top[x]],seg[x],1);
x=fa[top[x]];
}
if(dep[x]>dep[y])swap(x,y);
add(seg[x],seg[y],1);
}
int Tquery(int x,int y)
{
int res=0;
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]])swap(x,y);
res+=query(seg[top[x]],seg[x],1);
res%=p;
x=fa[top[x]];
}
if(dep[x]>dep[y])swap(x,y);
res+=query(seg[x],seg[y],1);
return res%p;
}
void Treeadd(int x,int z)
{
add(seg[x],seg[x]+size[x]-1,1);
}
int Treequery(int x)
{
return query(seg[x],seg[x]+size[x]-1,1);
}
//---------------以上为树链剖分----------------
//---------------以下为预处理------------------
void dfs1(int node,int father)
{
fa[node]=father;
dep[node]=dep[father]+1;
size[node]=1;
int maxson=-1;
for(int i=head[node];i;i=nxt[i])
{
int go=v[i];
if(go==father)continue;
dfs1(go,node);
size[node]+=size[go];
if(size[go]>maxson)son[node]=go,maxson=size[go];
}
}
void dfs2(int node,int topfather)
{
seg[node]=++id;
top[node]=topfather;
w[id]=num[node];
if(!son[node])return;
dfs2(son[node],topfather);
for(int i=head[node];i;i=nxt[i])
{
int go=v[i];
if(go==fa[node]||go==son[node])continue;
dfs2(go,go);//轻儿子是重链的顶端.
}
}
//---------------以上为预处理------------------
//---------------以下为主函数------------------
signed main()
{
//freopen("1.in","r",stdin);
n=read();m=read();r=read();p=read();
for(int i=1;i<=n;i++)num[i]=read();
for(int i=1;i<n;i++)
{
x=read();y=read();
add(x,y);add(y,x);
}
dfs1(r,0);dfs2(r,r);
build(1,n,1);
while(m--)
{
q=read();
if(q==1)
{
x=read();y=read();z=read();
Tadd(x,y);
}
else if(q==2)
{
x=read();y=read();
cout<<Tquery(x,y)<<endl;
}
else if(q==3)
{
x=read();z=read();
Treeadd(x,z);
}
else
{
x=read();
cout<<Treequery(x)<<endl;
}
}
return 0;
}
原文：https://www.cnblogs.com/szmssf/p/11132365.html