1.樹鍊剖分的用處
對如下問題我們可以采用樹鍊剖分的方法去做
1.把某個節點的子樹的每個節點都加上一個值z
2.查詢某個節點的子樹的所有節點的值的和求出來
3.把一個節點x到y之間最短路徑（經過邊的條數最少）上的每個節點都加上某個值z
4.把一個節點x到y之間最短路徑（經過邊的條數最少）上的所有節點的和求出來
由于我們需要解決這些問題，是以我們要使用樹鍊剖分這種算法。
2.實作原理：
1.知識儲備：
重兒子：該節點的所有兒子中，子樹中節點個數最多的兒子。
舉例：節點A有兩個兒子，G所形成的樹中有6個結點分别為 G B E V J T {GBEVJT} GBEVJT，C所形成的樹中有5個結點 C F D Z X {CFDZX} CFDZX。是以A的重兒子為G。對于j結點E，它的兩個兒子的大小相同，于是重兒子可以是任何一個兒子。
2.操作
我們按照每一個結點的重兒子走就形成了一條重鍊，如圖
我們要找出這個圖上的所有重鍊，如圖
這個書上就兩條重鍊，你找不出第3個了。
然後我們按重鍊的順序為結點打上時間戳。重鍊按順序打，其餘的按照dfs的順序打。如圖
我們定義這樣幾個數組完成重鍊剖分
int
fa[N],//記錄該節點的父親
dep[N],//記錄該節點的深度
son[N],// 記錄重兒子
siz[N],//記錄該節點子樹的大小（包含該節點）
top[N],//記錄該重鍊的頂部
dfn[N],//時間戳
w[N],//
tim;//計數器
void dfs1(int u,int f)//處理fa，dep，siz，so
{
dep[u]=dep[f]+1;
fa[u]=f;
siz[u]=1;//目前節點的大小初始化為1（因為該節點本身算一個嘛）
int maxx=-1;
for(int i=head[u]; ~i; i=edge[i].next)
{
int v=edge[i].v;
if(v==f)
continue;//因為存的是無向圖，是以一個邊存兩次，可能會回到該節點的父親節點
dfs1(v,u);
siz[u]+=siz[v];
if(siz[v]>maxx)
{
son[u]=v;
maxx=siz[v];
}
}
}
void dfs2(int u,int t)//處理dfn，top，w，t為該鍊的頭
dfn[u]=++tim;
top[u]=t;
w[tim]=v[u];
if(!son[u])
return;
dfs2(son[u],t);
for(int i=head[u]; ~i; i=edge[i].next)
{
int v=edge[i].v;
if(v==fa[u]||v==son[u])
continue;
dfs2(v,v);
}
}
操作完成。解釋一下為什麼要這樣做。
通過這樣做我們強行把樹的結點拆成一個連續的數組： A G E J T B V C F D X Z {AGEJTBVCFDXZ} AGEJTBVCFDXZ
假設 A G E J T B V C F D X Z {AGEJTBVCFDXZ} AGEJTBVCFDXZ每個字母代表該節點存的值，然後你按照我說的來觀察一下如果我要求以G為根的子樹上的和（即實作操作2）是不是就是對數組 A G E J T B V C F D X Z {AGEJTBVCFDXZ} AGEJTBVCFDXZ從下标2到2+size-1求和。（2是我們按照數鍊剖分為G打的時間戳，size為以G為根的子樹的大小。）
同理适用于所有的結點，你可以看一下。
那麼我要實作操作1，與上面同理。
為什麼可以這樣呢？因為我們強行把樹搞成了一個連續的，你觀察一下是不是每棵子樹都是一組連續的數。
到此為止，操作1和操作2就解釋完了。下面來解釋一下操作3和操作4怎麼通過我們以上的處理來解決
3.把一個節點x到y之間最短路徑（經過邊的條數最少）上的每個節點都加上某個值z
4.把一個節點x到y之間最短路徑（經過邊的條數最少）上的所有節點的和求出來
以操作4為例，可以分成以下幾種情況
看圖：
我們可以發現：任何一條路徑都是由重鍊的一部分和葉子結點組成的。
1. x和y在一條重鍊上：
因為每個重鍊都是連續的是以我們可以直接求。eg：求G+E+J我們就可以在數組 A G E J T B V C F D X Z AGEJTBVCFDXZ AGEJTBVCFDXZ中求下标2~4的和。
2. 如果不在一條重鍊上：
引理：除根節點以外的任何一個結點的父親都在一條重鍊上。
證明：因為父親節點存在兒子是以一定存在重兒子，是以一定在一條重鍊上。
我嘴笨，還是舉例子比較好講。
對X到J最短路徑進行求和，我們要維護兩個指針
我們選所在鍊頂端較深的那一個進行操作，J的頂端為G，X的頂端為F，顯然F的深度較深，是以我們把指向X的指針從X跳到F，邊跳邊求和，加到F後再往上跳，跳到F的父親節點。由引理可知：P還是在一條重鍊上。于是無限循環，直到兩指針跳到同一個結點貨同一個重鍊上就解決了問題。
劃重點：我們可以套一個線段樹實作上面的區間求和，和區間修改操作。
洛谷重鍊剖分模闆題
題解：
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
const double PI = atan(1.0)*4.0;
typedef long long ll;
const int N=1e5+50;
int mod;
int dfn[N],dep[N],top[N],fa[N],son[N],siz[N],w[N],tim;
struct node
{
int l,r;
ll data;
int plz;
} a[4*N];
void build(int now,int l,int r)
{
a[now].plz=0;
a[now].l=l;
a[now].r=r;
if(l==r)
{
a[now].data=w[l];
return;
}
int mid=l+r>>1;
build(now<<1,l,mid);
build(now<<1|1,mid+1,r);
a[now].data=a[now<<1].data+a[now<<1|1].data;
}
void pushdown(int now)
{
if(a[now].plz!=0)
{
a[now<<1].plz+=a[now].plz;
a[now<<1|1].plz+=a[now].plz;
a[now<<1].data+=a[now].plz*(a[now<<1].r-a[now<<1].l+1);
a[now<<1|1].data+=a[now].plz*(a[now<<1|1].r-a[now<<1|1].l+1);
a[now].plz=0;
}
return;
}
void updata(int now,int l,int r,int val)
{
if(l>a[now].r||r<a[now].l)
return ;
if(a[now].l>=l&&a[now].r<=r)
{
a[now].plz+=val;
a[now].data+=val*(a[now].r-a[now].l+1);
return;
}
pushdown(now);
if(a[now<<1].r>=l)
updata(now<<1,l,r,val);
if(a[now<<1|1].l<=r)
updata(now<<1|1,l,r,val);
a[now].data=a[now<<1].data+a[now<<1|1].data;
}
ll query(int now,int l,int r)
{
if(l>a[now].r||r<a[now].l)
return 0;
if(a[now].l>=l&&a[now].r<=r)
return a[now].data;
pushdown(now);
ll ans=0;
if(a[now<<1].r>=l)
ans+=query(now<<1,l,r);
if(a[now<<1|1].l<=r)
ans+=query(now<<1|1,l,r);
return ans%mod;
}
struct Node
{
int u,v,next;
} edge[2*N];
int head[N],cnt;
void add(int u,int v)
{
edge[cnt].u=u;
edge[cnt].v=v;
edge[cnt].next=head[u];
head[u]=cnt;
cnt++;
}
int v[N];
void dfs1(int u,int f)//fa,dep,son siz
{
dep[u]=dep[f]+1;
fa[u]=f;
siz[u]=1;
int maxx=-1;
for(int i=head[u]; ~i; i=edge[i].next)
{
int v=edge[i].v;
if(v==f)
continue;
dfs1(v,u);
siz[u]+=siz[v];
if(siz[v]>maxx)
{
son[u]=v;
maxx=siz[v];
}
}
}
void dfs2(int u,int t)//dfn,top
{
dfn[u]=++tim;
top[u]=t;
w[tim]=v[u];
if(!son[u])
return;
dfs2(son[u],t);
for(int i=head[u]; ~i; i=edge[i].next)
{
int v=edge[i].v;
if(v==fa[u]||v==son[u])
continue;
dfs2(v,v);
}
}
void updatachain(int x,int y,int z)
{
z=z%mod;
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]])
swap(x,y);
updata(1,dfn[top[x]],dfn[x],z);
x=fa[top[x]];
}
if(dep[x]>dep[y])
swap(x,y);
updata(1,dfn[x],dfn[y],z);
}
int querychain(int x,int y)
{
int res=0;
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]])
swap(x,y);
res=(res+query(1,dfn[top[x]],dfn[x]))%mod;
x=fa[top[x]];
}
if(dep[x]>dep[y])
swap(x,y);
res=(res+query(1,dfn[x],dfn[y]))%mod;
return res%mod;
}
void init()
{
for(int i=1; i<=N; i++)
head[i]=-1;
cnt=0;
tim=0;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
freopen("E:\\in.txt","r",stdin);
init();
int n,m,r;
cin>>n>>m>>r>>mod;
for(int i=1; i<=n; i++)
{
cin>>v[i];
}
for(int i=1; i<n; i++)
{
int x,y;
cin>>x>>y;
add(x,y);
add(y,x);
}
dfs1(r,0);
dfs2(r,r);
build(1,1,n);
for(int i=1; i<=m; i++)
{
int p,x,y,z;
cin>>p;
if(p==1)
{
cin>>x>>y>>z;
updatachain(x,y,z);
}
if(p==2)
{
cin>>x>>y;
cout<<querychain(x,y)<<endl;
}
if(p==3)
{
cin>>x>>z;
updata(1,dfn[x],dfn[x]+siz[x]-1,z);
}
if(p==4)
{
cin>>x;
cout<<query(1,dfn[x],dfn[x]+siz[x]-1)<<endl;
}
}
}