树链剖分入门

发表于 | 分类于 |

我们先来看这么个题：

给你一棵树，每次可能修改一条路径上的值，或是修改一整棵子树上的值，现在有多次查询，要查询一条链上的最大值（或是和），或是查询一棵子树上的最大值(或是和)。模板题，我们考虑最暴力的做法，对于每一条链，求LCA，然后暴力修改，这不用想就知道绝对要凉。那么我们想一想，如果我们维护的不是一棵树，而是一个链，那么我们有很多种方法来维护了(线段树，树状数组，主席树，分块等等等等)，那么我们是不是只要把一棵树变成一条链就可以了？

那么我们考虑最简单的变法：$dfs$序。具体的操作我们发现有很多种，这里介绍最简单的一种(除了这种其他都不会系列)叫轻重边剖分。那么我们先来搞个定义：对于树上的每一个节点，$size_i$表示i号节点的子树大小，那么我们在定义对于一个节点的所有子树，$size$最大的儿子就是这个节点的重儿子，另外的都是轻儿子，连接重儿子和父亲的边叫重边，其余的叫轻边，由多条重边组成的路径就叫重路径。

直观的就是下图：

红边即重边

嗯，好，那么接下来的事就很简单了：我们对整棵树进行dfs，优先扫重边。这样的话一条重链上的点的dfn就是连续的，所以我们对重链就可以快速修改了：对于每一条路径，我们可以将其拆分成多条重链和多条轻边，对于轻边，我们无视，应为轻边的两端一定是重链(特殊的，一个点也算重链)，所以，我们可以采用LCA的方式，每一次找出重链的顶点，然后逐层上推，知道两点会和。具体的看我代码吧(自认为还是非常清楚地)

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
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
#include<bits/stdc++.h>
using namespace std;
#define int long long 
inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
int num_edge,head[1000001],n,m,x,y,typ,cnt,root,mod,a,b,z,ans,ds[1000001];
struct node{
	int to,next;
}edge[10000001];
struct dhu{
	int l,r,dis,laze_tag;
}tree[10000001];
void add_edge(int from,int to)
{
	edge[++num_edge].to=to;
	edge[num_edge].next=head[from];
	head[from]=num_edge;
}
struct Jie{
	int max_son,z,zhong,size,father,dep,top,dfn;
}jie[1000001];
void dfs1(int a,int fa)
{
	jie[a].top=a;
	jie[a].father=fa;
	jie[a].dep=jie[jie[a].father].dep+1;
	jie[a].size=1;
	for(int i=head[a];i;i=edge[i].next)
	{
		if(edge[i].to!=fa)
		{
		dfs1(edge[i].to,a);
		jie[a].size+=jie[edge[i].to].size;
		if(jie[a].max_son<jie[edge[i].to].size)
		jie[a].zhong=edge[i].to,jie[a].max_son=jie[edge[i].to].size;
		}
	}
}
void dfs2(int a,int fa,int to)
{
	if(jie[a].dfn!=0||a==0)
	return ;
	jie[a].dfn=++cnt;
	ds[cnt]=a;
	jie[a].top=to;
	dfs2(jie[a].zhong,a,to);
	for(int i=head[a];i;i=edge[i].next)
	{
		if(edge[i].to!=fa)
		{
		if(edge[i].to!=jie[a].zhong)
		dfs2(edge[i].to,a,edge[i].to);
		}
	}
}
void build(int no,int s,int l)
{
	tree[no].l=s;
	tree[no].r=l;
	if(tree[no].l==tree[no].r)
	{
		tree[no].dis=jie[ds[l]].z;
		return ;
	}
	build(no*2,s,(s+l)/2);
	build(no*2+1,(s+l)/2+1,l);
	tree[no].dis=tree[no*2+1].dis+tree[no*2].dis;
}
void xie(int ji,int l,int r,int z)
{
	if(tree[ji].l>r||tree[ji].r<l)
	return ;
	else if(tree[ji].l>=l&&tree[ji].r<=r)
	{
		if(tree[ji].l==tree[ji].r)
		{
			tree[ji].dis+=z;
			tree[ji].dis%=mod;
			return ;
		}
		tree[ji].laze_tag+=z;
		return ;
	}
	else {
	xie(ji*2,l,r,z),xie(ji*2+1,l,r,z);	
	tree[ji].dis=tree[ji*2].dis+tree[ji*2].laze_tag*(tree[ji*2].r-		           tree[ji*2].l+1)+tree[ji*2+1].dis+tree[ji*2+1].laze_tag*(tree[ji*2+1].r-tree[ji*2+1].l+1);
	tree[ji].dis%=mod;
	}
}
int look(int ji,int l,int r)
{
//	cout<<ji<<" ";
	if(tree[ji].l>r||tree[ji].r<l)
	return 0;
	if(tree[ji].l==tree[ji].r)
	{
		return (tree[ji].dis+tree[ji].laze_tag)%mod;
	}
	else if(tree[ji].l>=l&&tree[ji].r<=r)
	{
		tree[ji].dis+=(tree[ji].r-tree[ji].l+1)*tree[ji].laze_tag;
		tree[ji].dis%=mod;
		tree[ji*2].laze_tag+=tree[ji].laze_tag;
		tree[ji*2+1].laze_tag+=tree[ji].laze_tag;
		tree[ji].laze_tag=0;
		return tree[ji].dis;
	}
	else {
		tree[ji].dis+=(tree[ji].r-tree[ji].l+1)*tree[ji].laze_tag;
		tree[ji].dis%=mod;
		tree[ji*2].laze_tag+=tree[ji].laze_tag;
		tree[ji*2+1].laze_tag+=tree[ji].laze_tag;
		tree[ji].laze_tag=0;
		return (look(ji*2,l,r)+look(ji*2+1,l,r))%mod;
	}
}
void test(int a)
{
//	cout<<"test:\n";
	cout<<tree[a].l<<" "<<tree[a].r<<" "<<tree[a].dis<<" "<<tree[a].laze_tag<<endl;
	if(tree[a].l!=tree[a].r)
	{
		test(a*2);
		test(a*2+1);
	}
//	cout<<"test end\n";
}
void test1()
{
	for(int i=1;i<=n;i++)
	{
		
		cout<<jie[i].dep<<" "<<jie[i].dfn<<" "<<jie[i].father<<" "<<jie[i].max_son<<" "<<jie[i].size<<" "<<jie[i].top<<" "<<jie[i].z<<" "<<jie[i].zhong;
		cout<<endl;	
	}
}
signed main()
{
	n=read();
	m=read();
	root=read();
	mod=read();
	for(int i=1;i<=n;i++)
	{
		jie[i].z=read();
	}
	for(int i=1;i<n;i++)
    {
    	a=read();
    	b=read();
    	add_edge(a,b);
    	add_edge(b,a);
	}
	dfs1(root,0);
	dfs2(root,0,root);
	build(1,1,n);
//	test1(); 
	for(int i=1;i<=m;i++)
	{
		typ=read();
		if(typ==1)
		{
			x=read();
			y=read();
			z=read();
			while(jie[x].top!=jie[y].top)
			{
				if(jie[jie[x].top].dep<jie[jie[y].top].dep)
				swap(x,y);
				xie(1,jie[jie[x].top].dfn,jie[x].dfn,z);
				x=jie[jie[x].top].father;
			}
			if(jie[x].dep>jie[y].dep)
			swap(x,y);
			xie(1,jie[x].dfn,jie[y].dfn,z);
		}
		if(typ==2)
		{
			x=read();
			y=read();
			//cout<<endl<<jie[x].dfn<<" "<<jie[y].dfn<<endl;
			ans=0;
			while(jie[x].top!=jie[y].top)
			{
				if(jie[jie[x].top].dep<jie[jie[y].top].dep)
				swap(x,y);
				ans+=look(1,jie[jie[x].top].dfn,jie[x].dfn);
				x=jie[jie[x].top].father;
			}
			if(jie[x].dep>jie[y].dep)
			swap(x,y);
			ans+=look(1,jie[x].dfn,jie[y].dfn);
			cout<<ans%mod<<endl;
		}
		if(typ==3)
		{
			x=read();
			z=read();
			xie(1,jie[x].dfn,jie[x].dfn+jie[x].size-1,z);  
            //对于一棵子树，他们的dfn许是连续的所以我们可以直接从线段树上修改。
		}
		if(typ==4)
		{
			x=read();
			cout<<look(1,jie[x].dfn,jie[x].dfn+jie[x].size-1)<<endl;
		}	
	}
}
-------------end.thanks for reading-------------