解决树上的很多问题。比如子树操作，链操作等等，但是不能处理动态问题（处理动态树问题大都要用 LCT）。
树链剖分同可持久化线段树一样，只是一个工具，难点都在维护的东西上。像什么树上 DDP，就是用树链剖分维护，难点全在列矩阵上。（用完全平衡二叉树可以更快，但没必要）
树链剖分就是利用了重链剖分剖出来之后每个点到根节点都最多只会跳 log 条重链。而 dfs 序按照先重儿子再其它儿子的顺序排，就可以让所有重链的编号连续。而连续，就可以在线段树上维护。（平衡树也可以。平衡树可以翻转区间，不过树链剖分都是静止的，翻转也用不着。）
重链剖分就是哪个儿子的子树内节点比较多就认那个儿子当重儿子，其它儿子就是它们的重链的顶端。
对于链上操作，链的两个端点，哪个的当前重链的深度深就把这条链修改，然后跳到重链顶端的父亲节点，再继续，直到它们在同一条重链上。然后在最后这 2 个点的区间内再做一次修改。
对于子树操作，记录每个点的子树遍历完之后出来时的 dfs 序编号，这个就是当前子树在线段树上的区间末尾（区间起点是这个点的 dfs 序）。
点击查看代码
#include <bits/stdc++.h>
using namespace std;
const int MAXN=1e6+50;
int N,M,Root,P;
long long Val[MAXN];
struct Edge
{
int x,y,Next;
}e[MAXN<<1];
int elast[MAXN],tot;
void Add(int x,int y)
{
tot++;
e[tot].x=x;
e[tot].y=y;
e[tot].Next=elast[x];
elast[x]=tot;
}
int Size[MAXN],Son[MAXN],Top[MAXN],father[MAXN],depth[MAXN];
int Id[MAXN],CntId,Back[MAXN];
long long Length[MAXN];
void dfs1(int u,int fa)
{
depth[u]=depth[fa]+1;
Size[u]=1;
father[u]=fa;
for(int i=elast[u];i;i=e[i].Next)
{
int v=e[i].y;
if(v==fa)
continue;
dfs1(v,u);
Size[u]+=Size[v];
if(Size[v]>Size[Son[u]])
{
Son[u]=v;
}
}
}
int In[MAXN],Out[MAXN];
void dfs2(int u,int fa,int zuzong)
{
Top[u]=zuzong;
Id[u]=++CntId;
In[u]=CntId;
Back[CntId]=u;
if(Son[u])
{
dfs2(Son[u],u,zuzong);
}
for(int i=elast[u];i;i=e[i].Next)
{
int v=e[i].y;
if(v==fa||v==Son[u])
continue;
dfs2(v,u,v);
}
Out[u]=CntId;
}
long long Sum[MAXN<<2],Lazy[MAXN<<2];
void PushDown(int u)
{
Lazy[u<<1]=(Lazy[u<<1]+Lazy[u])%P;
Lazy[u<<1|1]=(Lazy[u<<1|1]+Lazy[u])%P;
Sum[u<<1]=(Sum[u<<1]+Lazy[u]*Length[u<<1])%P;
Sum[u<<1|1]=(Sum[u<<1|1]+Lazy[u]*Length[u<<1|1])%P;
Lazy[u]=0;
}
void Build(int u,int l,int r)
{
if(l==r)
{
Sum[u]=Val[Back[l]];
Length[u]=1;
return;
}
int Mid=l+r>>1;
Build(u<<1,l,Mid);
Build(u<<1|1,Mid+1,r);
Sum[u]=(Sum[u<<1]+Sum[u<<1|1])%P;
Length[u]=Length[u<<1]+Length[u<<1|1];
}
void Modify(int u,int l,int r,int x,int y,long long k)
{
if(x<=l&&r<=y)
{
Sum[u]=(Sum[u]+Length[u]*k)%P;
Lazy[u]=(Lazy[u]+k)%P;
return;
}
if(Lazy[u])
PushDown(u);
int Mid=l+r>>1;
if(x<=Mid&&y>=l)
{
Modify(u<<1,l,Mid,x,y,k);
}
if(x<=r&&y>=Mid+1)
{
Modify(u<<1|1,Mid+1,r,x,y,k);
}
Sum[u]=(Sum[u<<1]+Sum[u<<1|1])%P;
}
long long Query(int u,int l,int r,int x,int y)
{
if(x<=l&&r<=y)
{
return Sum[u];
}
if(Lazy[u])
PushDown(u);
int Mid=l+r>>1;
long long NowSum=0;
if(x<=Mid&&y>=l)
NowSum=(NowSum+Query(u<<1,l,Mid,x,y))%P;
if(x<=r&&y>=Mid+1)
NowSum=(NowSum+Query(u<<1|1,Mid+1,r,x,y))%P;
return NowSum;
}
int main()
{
scanf("%d%d%d%d",&N,&M,&Root,&P);
for(int i=1;i<=N;i++)
{
scanf("%lld",&Val[i]);
}
for(int i=1;i<N;i++)
{
int x,y;
scanf("%d%d",&x,&y);
Add(x,y);
Add(y,x);
}
dfs1(Root,0);
dfs2(Root,0,Root);
Build(1,1,N);
while(M--)
{
int op,x,y;
long long z;
scanf("%d%d",&op,&x);
if(op==1)
{
scanf("%d%lld",&y,&z);
while(Top[x]!=Top[y])
{
if(depth[Top[x]]<depth[Top[y]])
swap(x,y);
Modify(1,1,N,In[Top[x]],In[x],z);
x=father[Top[x]];
}
if(depth[x]<depth[y])
swap(x,y);
Modify(1,1,N,In[y],In[x],z);
}
if(op==2)
{
scanf("%d",&y);
long long NowSum=0;
while(Top[x]!=Top[y])
{
if(depth[Top[x]]<depth[Top[y]])
swap(x,y);
NowSum=(NowSum+Query(1,1,N,In[Top[x]],In[x]));
x=father[Top[x]];
}
if(depth[x]<depth[y])
swap(x,y);
NowSum=(NowSum+Query(1,1,N,In[y],In[x]))%P;
printf("%lld\n",NowSum);
}
if(op==3)
{
scanf("%lld",&z);
Modify(1,1,N,In[x],Out[x],z);
}
if(op==4)
{
printf("%lld\n",Query(1,1,N,In[x],Out[x]));
}
}
}
今年二月我写过一次模板，一直 WA20 分，后来才调对。今天写，又 WA20 分，跟之前那次一模一样。错误原因竟然是——区间加一个数区间和数组真就只加了这个数，没乘区间长度。下次一定不要再犯这样的错误了。
标签：剖分,NowSum,int,long,树链,重链 From： https://www.cnblogs.com/0htoAi/p/16705777.html