树相关——树链剖分(轻重链剖分)

先把线段树学了再来看这篇博客

树链剖分引入

 我们来看一个例子：
 在树上的两个点的最短路径上的所有点的值加上$c$。对于每次询问，求出树上任意两点的最短距离。

 如果这是一个离线的问题，直接就用树上差分+$dfs$即可解决。但是如果这个问题是在线的，我们就不得不需要一种在线的数据结构来解决这个问题。于是，在这里我们引入树链剖分。

树链剖分基本概念

基本概念：
1.重儿子：假设$x$有$n$个儿子节点，在$n$个节点中以$y$儿子节点的为根子树大小最大，那么$y$就是$x$的重儿子
2.轻儿子：除重儿子外的所有儿子均为轻儿子
3.轻边：$x$与轻儿子相连的边
4.重边：$x$与重儿子相连的边
5.轻链：均由轻儿子构成的一条链（一条轻链不一定只有一个节点）
6.重链：均由重儿子构成的一条链

我们以下图来举一个例子：

 如上图所示，$3$就是$1$的重儿子，$5$是$2$的重儿子，$1->3->6->9->10$和$2->5->8$就是一条重链。(1,3)就是一条重边。(3,7)就是一条轻边。

第一部分——预处理部分

我们需要的信息如下
 $dep[x]$：$x$节点的深度
 $fa[x]$：$x$节点的父亲节点
 $son[x]$：$x$节点的重儿子
 $siz[x]$：$x$节点为根的子树大小
 $top[x]$：$x$节点所在链的顶点

 如何得到这些信息呢？$dfs$可以考虑一下。

 我们用一个$dfs$维护前四个信息。代码入下。

void dfs1(int u,int father){
	dep[u]=dep[father]+1,fa[u]=father,siz[u]=1;
	for(int e=first[u];e;e=nex[e]){
		int v=to[e];
		if(v==fa[u])continue;
		dfs1(v,u);
		siz[u]+=siz[v];
		if(siz[v]>siz[son[u]])son[u]=v;
	}
}
1
2
3
4
5
6
7
8
9
10

 接下来获取$top[x]$，我们处理的方式：优先对重儿子处理，重儿子处理结束后再处理轻儿子（新开链。
 浅浅地讲一下为什么要先搜重儿子。因为我们要维护的是重链，而一条链的要求必须是连续的，而我们维护时使用数据结构，必然是要将它转换到数列上来做的，如何转换呢？最好的方法就是按照$dfs$ 序，此时如果不先搜重儿子的话，重链上的$dfs$序就可能会断掉，如下图。

void dfs2(int u,int f){
	top[u]=f;dfn[u]=++cnt;nv[cnt]=a[u];//nv[]为接下来的线段树准备
	if(son[u]) dfs2(son[u],f);
	for(int e=first[u];e;e=nex[e]){
		int v=to[e];
		if(v==fa[u] or v==son[u])continue;
		dfs2(v,v);
	}
}
1
2
3
4
5
6
7
8
9

线段树部分

不要告诉我你不会线段树？

修改 and 查询

 因为要维护的是链，而且我们现在已经保证链上的$dfs$序连续了，所以我们直接取结点$x$的$top[x]$到它自己这一段进行修改或查询（即使用$dfs$序修改），然后再将当前结点跳到它的$fa[top[x]]$即可。为了防止一个结点无限往上跳，我们每次都选$top$值比较深的那个结点进行修改/查询，再往上跳，就可以防止无限跳的情况了。
 而如果选的是浅的，而它又往上跳，则深度越来越浅，必然会无限跳，最终死循环。
 最后，这两个结点一定会到一条链上，而且必然有一个点会是$LCA$，我们最后进行一次操作即可。

void addPath(int x,int y,int k){
	k%=P;int fx=top[x],fy=top[y];
	while(fx!=fy)
		if(dep[fy]>dep[fx]) swap(fy, fx),swap(y,x);
		else{
			update(1,dfn[fx],dfn[x],k);
			x=fa[fx],fx=top[x];
		}
	if(dfn[x]<=dfn[y])update(1,dfn[x],dfn[y],k);
	else update(1,dfn[y],dfn[x],k);
}

int findPath(int x,int y){
	int ans=0,fx=top[x],fy=top[y];
	while(fx!=fy)
		if(dep[fx]<dep[fy])swap(fx,fy),swap(x,y);
		else{
			ans=(ans+query(1,dfn[fx],dfn[x]))%P;
			x=fa[fx],fx=top[x];
		}
	if(dfn[x]<=dfn[y])ans=(ans+query(1,dfn[x],dfn[y]))%P;
	else ans=(ans+query(1,dfn[y],dfn[x]))%P;
	return ans%P;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

查询子树 and 修改子树如下：

inline void AddSubtree(int x,int k){update(1,dfn[x],dfn[x]+siz[x]-1,k);}

inline int FindSubtree(int x){return query(1,dfn[x],dfn[x]+siz[x]-1)%P;}
1
2
3

完整代码

#include
#define in read()
#define MAXN 100050
#define MAXM MAXN<<2
#define re register
#define ls p<<1
#define rs p<<1|1
#define int long long
using namespace std;

struct SGT{
	int l,r,sum,sumtag;
}t[MAXM];

int n,m,rt,P,a[MAXN];
int nex[MAXM],first[MAXN],to[MAXM],tot=0;
int dep[MAXN],fa[MAXN],siz[MAXN],top[MAXN],son[MAXN],dfn[MAXN],nv[MAXN],cnt=0;

inline int read(){
	int x=0,f=1;char c=getchar();
	while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
	while(isdigit(c)){x=(x<<3)+(x<<1)+c-'0';c=getchar();}
	return x*f;
}
 
inline void addedge(int u,int v){
	nex[++tot]=first[u];
	first[u]=tot;
	to[tot]=v;
}

inline void pushup(int p){t[p].sum=t[ls].sum+t[rs].sum;}

inline void pushdown(int p){
	if(t[p].sumtag){
		t[ls].sum=(t[ls].sum%P+t[p].sumtag*(t[ls].r-t[ls].l+1)%P)%P;
		t[rs].sum=(t[rs].sum%P+t[p].sumtag*(t[rs].r-t[rs].l+1)%P)%P;
		t[ls].sumtag=(t[ls].sumtag%P+t[p].sumtag%P)%P;
		t[rs].sumtag=(t[rs].sumtag%P+t[p].sumtag%P)%P;
		t[p].sumtag=0;
	}
}

void build(int p,int l,int r){
	t[p].l=l,t[p].r=r;
	if(l==r){t[p].sum=nv[l];return;}
	int mid=(l+r)>>1;
	build(ls,l,mid),build(rs,mid+1,r);
	pushup(p);
}

void update(int p,int l,int r,int v){
	if(l<=t[p].l and t[p].r<=r){t[p].sum+=v*(t[p].r-t[p].l+1);t[p].sumtag+=v;return;}
	pushdown(p);
	int mid=(t[p].l+t[p].r)>>1;
	if(l<=mid)update(ls,l,r,v);
	if(r>mid) update(rs,l,r,v);
	pushup(p);
}

int query(int p,int l,int r){
	if(l<=t[p].l and t[p].r<=r){return t[p].sum;}
	pushdown(p);
	int ans=0,mid=(t[p].l+t[p].r)>>1;
	if(l<=mid)ans=(ans+query(ls,l,r))%P;
	if(r>mid) ans=(ans+query(rs,l,r))%P;
	return ans%P;
}

void dfs1(int u,int father){
	dep[u]=dep[father]+1,fa[u]=father,siz[u]=1;
	for(int e=first[u];e;e=nex[e]){
		int v=to[e];
		if(v==fa[u])continue;
		dfs1(v,u);
		siz[u]+=siz[v];
		if(siz[v]>siz[son[u]])son[u]=v;
	}
}

void dfs2(int u,int f){
	top[u]=f;dfn[u]=++cnt;nv[cnt]=a[u];
	if(son[u]) dfs2(son[u],f);
	for(int e=first[u];e;e=nex[e]){
		int v=to[e];
		if(v==fa[u] or v==son[u])continue;
		dfs2(v,v);
	}
}

void addPath(int x,int y,int k){
	k%=P;int fx=top[x],fy=top[y];
	while(fx!=fy)
		if(dep[fy]>dep[fx]) swap(fy, fx),swap(y,x);
		else{
			update(1,dfn[fx],dfn[x],k);
			x=fa[fx],fx=top[x];
		}
	if(dfn[x]<=dfn[y])update(1,dfn[x],dfn[y],k);
	else update(1,dfn[y],dfn[x],k);
}

int findPath(int x,int y){
	int ans=0,fx=top[x],fy=top[y];
	while(fx!=fy)
		if(dep[fx]<dep[fy])swap(fx,fy),swap(x,y);
		else{
			ans=(ans+query(1,dfn[fx],dfn[x]))%P;
			x=fa[fx],fx=top[x];
		}
	if(dfn[x]<=dfn[y])ans=(ans+query(1,dfn[x],dfn[y]))%P;
	else ans=(ans+query(1,dfn[y],dfn[x]))%P;
	return ans%P;
}

inline void AddSubtree(int x,int k){update(1,dfn[x],dfn[x]+siz[x]-1,k);}

inline int FindSubtree(int x){return query(1,dfn[x],dfn[x]+siz[x]-1)%P;}

signed main(){
	n=in,m=in,rt=in,P=in;
	for(re int i=1;i<=n;i++)a[i]=in;
	for(re int i=1;i<=n-1;i++){
		int u=in,v=in;
		addedge(u,v),addedge(v,u);
	}
	dfs1(rt,0);
	dfs2(rt,rt);
	build(1,1,n);
	for(re int i=1;i<=m;i++){
		int opt=in;
		if(opt==1){
			int x=in,y=in,z=in;
			addPath(x,y,z);
		}
		if(opt==2){
			int x=in,y=in;
			cout<<findPath(x,y)%P<<'\n';
		}
		if(opt==3){
			int x=in,z=in;
			AddSubtree(x,z);
		} 
		if(opt==4){
			int x=in;
			cout<<FindSubtree(x)%P<<'\n';
		}
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150