文章目录
树链剖分，可以把一棵树划分成多条链，对于每条链可以用线段树等数据结构进行维护，将树形结构的问题转化。
常见的方法是轻重链剖分，即 Heavy-Light Decomposition。
[notice]这是一篇意识流式的总结，如果要入门树链剖分请不要看这篇……[/notice]
前置知识
LCA、线段树……
一些定义
需要构造如下数组：
size[x]：以 x 为根的子树的节点总数；deep[x]：x 的深度；son[x]：x 通过重链通向的儿子节点；fa[x]：x 的父节点；top[x]：x 所在重链的顶端节点；id[x]：节点 x 在线段树中的下标位置；v[x]：节点 x 的权值（对于边权，可以把边的权值归属于其下面的点，转化为点权处理）。
另建一棵线段树存储重链信息。
如果 v 是 u 的儿子中 size 最大的一个，则 (u,v) 是重边，v 是 u 的重儿子，u 通向的其他儿子是轻边。
连续的重边形成重链。通过 id[] 可以将一条重链映射到线段树上的一条线段。
关于复杂度的结论
结论一： 如果 为轻边，则 size[v] 不会大于 size[u]/2。
结论二： 重链和轻边的数量级相当。
由此可以得到：
结论三： 从某一个点到根上经过的重链或轻边的总数在 级别。这是树链剖分的核心。
据此，对于一条链上的操作可以做到 。对于链上的修改，整条重链可以对应线段树的一个区间，存储 top[] 可以实现直接调到重链顶端，达到优化时间复杂度的目的。
实现
第一遍 DFS 构造出 size[],son[],fa[],deep[]，第二遍 DFS 造出 top[],id[]。
对于两点的路径修改，直接求出 LCA 后一直往上跳即可。
对于子树修改，直接当成 DFS 序处理。
对于构造 id[] 的 DFS 需要注意：本质上 id[] 是一个时间戳，即 DFS 序。为了使得重边在造出来的序中连续，便于线段树的处理，在遍历的时候要先遍历重儿子。涉及子树的操作也会方便很多。
代码
洛谷模板题 P3384：
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
using namespace std;
// #define int long long
inline int read(){
int ret=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();}
while (ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
return ret*f;
}
const int maxn=1e5+5;
const int maxe=2*maxn;
int n,m,root,tt;
void add(int &x,int y){
x=(x+y%tt)%tt;
}
class SegmentTree{
#define mid (((tr-tl)>>1)+tl)
#define ls ((p<<1))
#define rs ((p<<1)+1)
private:
int tree[maxn*4],tag[maxn*4];
void push_down(int tl,int tr,int p){
add(tree[ls],tag[p]*(mid-tl+1)%tt);
add(tag[ls],tag[p]);
add(tree[rs],tag[p]*(tr-(mid+1)+1)%tt);
add(tag[rs],tag[p]);
tag[p]=0;
}
public:
SegmentTree(){
memset(tree,0,sizeof(tree));
memset(tag,0,sizeof(tag));
}
void update(int x,int tl,int tr,int p,int delta){
if (tl==tr && tl==x){
add(tree[p],delta);
return;
}
push_down(tl,tr,p);
if (x<=mid ) update(x,tl,mid,ls,delta);
if (mid+1<=x) update(x,mid+1,tr,rs,delta);
tree[p]=(tree[ls]+tree[rs])%tt;
}
void update(int sl,int sr,int tl,int tr,int p,int delta){
if (sl<=tl && tr<=sr){
add(tree[p],(tr-tl+1)*delta%tt);
add(tag[p],delta);
return;
}
push_down(tl,tr,p);
if (sl<=mid ) update(sl,sr,tl,mid,ls,delta);
if (mid+1<=sr) update(sl,sr,mid+1,tr,rs,delta);
tree[p]=(tree[ls]+tree[rs])%tt;
}
int query(int x,int tl,int tr,int p){
if (tl==tr && x==tl) return tree[p]%tt;
push_down(tl,tr,p);
int ret=0;
if (x<=mid ) add(ret,query(x,tl,mid,ls));
if (mid+1<=x) add(ret,query(x,mid+1,tr,rs));
return ret;
}
int query(int sl,int sr,int tl,int tr,int p){
if (sl<=tl && tr<=sr) return tree[p]%tt;
push_down(tl,tr,p);
int ret=0;
if (sl<=mid ) add(ret,query(sl,sr,tl,mid,ls));
if (mid+1<=sr) add(ret,query(sl,sr,mid+1,tr,rs));
return ret;
}
};
int tot=0,lnk[maxn],nxt[maxe],to[maxe];
int size[maxn],deep[maxn],fa[maxn];
int v[maxn];
void add_edge(int x,int y){
tot++;to[tot]=y;
nxt[tot]=lnk[x];lnk[x]=tot;
}
int f[maxn][25];
int get_lca(int x,int y){
if (deep[x]<deep[y]) swap(x,y);
for (int i=23;i>=0;i--) if (deep[f[x][i]] >= deep[y]) x=f[x][i];
if (x==y) return x;
for (int i=23;i>=0;i--) if (f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
return fa[x];
}
namespace HLD{
int son[maxn],top[maxn],id[maxn];
void make_tree(int x){
size[x]=1;
f[x][0]=fa[x];for (int i=1;i<=23;i++) f[x][i]=f[f[x][i-1]][i-1];
int max_size=0,k=-1;
for (int i=lnk[x];i;i=nxt[i]) if (to[i]!=fa[x]){
fa[to[i]]=x;deep[to[i]]=deep[x]+1;
make_tree(to[i]);
size[x]+=size[to[i]];
if (size[to[i]]>max_size) max_size=size[to[i]],k=to[i];
}
if (k!=-1) son[x]=k;
}
void make_chain(int x){
id[x]=++id[0];
if (son[fa[x]]!=x) top[x]=x; else top[x]=top[fa[x]];
if (son[x]) make_chain(son[x]);
for (int i=lnk[x];i;i=nxt[i]) if (to[i]!=fa[x] && to[i]!=son[x]){
make_chain(to[i]);
}
}
void change_single(int x,int l,int delta,SegmentTree &tree){
while (x!=l){
if (top[x]!=x){
if (deep[top[x]]>=deep[l]) tree.update(id[top[x]]+1,id[x],1,n,1,delta),x=top[x];
else tree.update(id[l]+1,id[x],1,n,1,delta),x=l;
} else tree.update(id[x],1,n,1,delta),x=fa[x];
}
tree.update(id[x],1,n,1,delta);
}
void change_chain(int x,int y,int delta,SegmentTree &tree){
int l=get_lca(x,y);
change_single(x,l,delta,tree);
change_single(y,l,delta,tree);
tree.update(id[l],1,n,1,-delta);
}
int query_single(int x,int l,SegmentTree &tree){
int ret=0;
while (x!=l){
if (top[x]!=x){
if (deep[top[x]]>=deep[l]) add(ret,tree.query(id[top[x]]+1,id[x],1,n,1)),x=top[x];
else add(ret,tree.query(id[l]+1,id[x],1,n,1)),x=l;
} else add(ret,tree.query(id[x],1,n,1)),x=fa[x];
}
add(ret,tree.query(id[x],1,n,1));
return ret;
}
int query_chain(int x,int y,SegmentTree &tree){
int l=get_lca(x,y);
return (query_single(x,l,tree)+query_single(y,l,tree)-tree.query(id[l],1,n,1)+tt)%tt;
}
void change_subtree(int x,int delta,SegmentTree &tree){
tree.update(id[x],id[x]+size[x]-1,1,n,1,delta);
}
int query_subtree(int x,SegmentTree &tree){
return tree.query(id[x],id[x]+size[x]-1,1,n,1);
}
}
SegmentTree tree;
signed main(){
n=read(),m=read(),root=read(),tt=read();
for (int i=1;i<=n;i++) v[i]=read();
for (int i=1;i<n;i++){
int x=read(),y=read();
add_edge(x,y);add_edge(y,x);
}
deep[root]=1;
HLD::make_tree(root);
HLD::make_chain(root);
for (int i=1;i<=n;i++) tree.update(HLD::id[i],1,n,1,v[i]);
while (m--){
int opt=read(),x,y,z;
switch(opt){
case 1:
x=read(),y=read(),z=read()%tt;
HLD::change_chain(x,y,z,tree);
break;
case 2:
x=read(),y=read();
printf("%d\n",HLD::query_chain(x,y,tree));
break;
case 3:
x=read(),z=read()%tt;
HLD::change_subtree(x,z,tree);
break;
case 4:
x=read();
printf("%d\n",HLD::query_subtree(x,tree));
break;
}
}
return 0;
}