树链剖分学习笔记

前些日子在洛谷上写LCA的时候用倍增算法被卡常数了,一气之下就去查了其他的LCA算法,看到tarjan和树剖都能解决这个问题,于是就选择了学习树剖这条(不归之)路.

以上全是废话

我看了很多大犇的博客才终于大概搞明白了树链剖分是个什么逻辑和思路.虽然大犇们写的都很详细了,但对于本蒟蒻来说还是有些不那么容易理解,因此在这里尝试自己重新解释一下树链剖分的思想和具体实现,同时添加一些自己的理解,来帮助理解这个实际上并不困难的算法.


树链剖分的基本思想

树链剖分或许更应该被称作一种思想,就是将一棵树拆分成几个部分,使每个部分内的元素之间都具有一定的联系,从而允许我们对进行过剖分的树利用一些其他的高级数据结构进行一些难以暴力解决的操作,如:

  • 将节点x到节点y的最短路径上的所有节点/边的权值加某个值
  • 将以节点x为根的子树中的所有节点/边的权值加某个值
  • 查询节点x到节点y的最短路径上的所有节点/边的权值之和
  • 查询以节点x为根的子树中的所有节点/边的权值之和
  • (还可以顺便求最近公共祖先LCA)

也就是说,树链剖分就如同它的名字一样,就是将树解剖成若干个部分(称为树链),方便后续的操作.

前置知识需求

在学习树链剖分之前,需要先行掌握如下的知识:

  • 树的基本概念
  • 图的基本概念
  • 深度优先搜索(DFS)
  • 线段树(或者树状数组)

基本概念

为了完成分解,需要计算几个辅助数组的值.首先定义一些概念(在概念名后面的括号内的是数组名):

  • 和普通树相同的概念(不详细解释了)
    • 父节点(f)
    • 子节点(head)
    • 大小(size)
    • 深度(dep)
  • 额外添加的概念
    • 重子节点(hson):节点的子节点中具有最大的size的一个(这类节点又称为重节点.特别的,根节点是重节点)
    • 轻子节点:除重子节点以外的所有节点(这类节点又称为轻节点)
    • 重边:连接父节点和重子节点的边
    • 轻边:连接父节点和轻子节点的边(除重边的所有边)
    • 重链:若干重边连接成的链(下文中也会称为树链)
    • 轻链:若干轻边连接成的链
    • 链顶(top):该节点所在的重链的顶端节点的序号(请注意,这里的序号与下文将出现的编号有所不同.序号是节点的原始编号,而编号的具体意义将在下文解释.)

为了确认自己是不是已经理解了这些概念,这里附上一张图,并给出某些数组在这种情况下的值.其中,重节点将在图中以红色标识,重边以粗线标识,轻边以细线标识.
示例来自百度百科

表格

表格似乎生成的有些问题,正在寻找解决方法,先用图片代替了.

值得注意的是,我们所有下标均从1开始,并以0表示不存在.

如果对于任意节点,我们在访问完后优先访问它的重子节点,并将所有节点按照访问顺序编号,将得到这样的一组编号:

编号(修改自百度百科图片)

仔细观察这两张图以及表格,能够发现如下性质:

  • 两个节点x,y在同一条重链上,当且仅当top[x]==top[y]
  • 任何一条重链上的点编号连续
  • 以任何一个点为根的子树中的所有点编号连续

事实上,这就是树剖得以解决问题的根本.因此,我们引入了一个新值编号(id):从根节点开始,对于任意节点,先访问其重子节点,然后再访问其其他节点所得到的某节点的访问次序编号.正是id具有的连续性,使得我们能够用线段树完成一些操作.

如何使用树剖的结果

在研究树剖的实现之前,先来看看在树剖完成后如何应用其结果.我们由简到繁的讨论如下几个应用:

将以节点x为根的子树中的所有节点/边的权值加某个值

我们假设已经实现了一棵线段树,其名称为t(一下应用中均包含此假设).

关于线段树的具体实现请看完整代码或是我关于线段树的学习笔记(暂时还没有).

显然,由于以任何一个点为根的子树中的所有点编号连续,这时只需要对以x的编号为起始点,x子树中编号最大的节点的编号为终止点的区间进行区间修改,就可以完成这个操作了.而由于连续,最大的点的编号就是x编号加上x的大小.因此,修改的区间就是$[id[x],id[x]+size[x])$.

查询以节点x为根的子树中的所有节点/边的权值之和

同理,只需要对区间进行区间求和就可以完成了,同样是线段树的基本操作.操作区间同样是$[id[x],id[x]+size[x])$.

求两个节点x和y的最近公共祖先(LCA)

显然,两个节点之间的最短路径会经过两个节点的最近公共祖先.因此,在研究对两点间最短路径上的操作之前,我们先来看看如何用树链剖分得到的数据求LCA.

显然,如果两个节点在同一条树链上,它们的LCA就是两点中深度较小的节点.这时可以直接得到结果:LCA=dep[x]>dep[y]?y:x.
而当两个节点不在同一树链上时,我们就可以利用top迅速的向上跳跃,来到另一条树链上,尽快的使两个节点到达同一条树链上.这也就解释了为什么我们的原则是”对于任意节点,先访问其重子节点,然后再访问其其他节点”:size的大小可以在一定程度上反映这棵子树的高度,将高度最大的一条作为重链可以使这上面的点迅速跳到顶端,减少跳跃次数,提高算法的效率.

需要注意的是,我们应该让跳跃后到达的链顶深度更大的点跳跃而另一个点保持不动.这样才能保证两个点不会擦肩而过.

编号(修改自百度百科图片)

比如这个例子中,我们若要求点11和12的LCA,我们若首先让11向上跳跃将到达2,而事实上11和12的LCA是6,这时已经不可能再得到正确的结果了.

代码也不难写出:

1
2
3
4
5
6
7
8
9
int lca(int x,int y)
{
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]]) swap(x,y);
x=f[top[x]];//注意这里,top[x]和x仍在同一树链上,要到达另外一条树链需要取top[x]的父节点
}
return dep[x]>dep[y]?y:x;
}

代码很简单,但是已经足够正确的求解LCA问题了.

将节点x到节点y的最短路径上的所有节点/边的权值加某个值

我们采用和上面求LCA一样的思路:不断使两个节点向上移动从而逼近,直到两个节点到达同一树链,这时即可一步完成最后一段的操作.

不难想到,为了实现这个操作,我们只需要在每一步移动x点的时候,修改移动经过的点的权值,就可以轻松完成任务了.由于”任何一条重链上的点编号连续”,我们的区间也很好确定:
两点在同一条树链上时,操作区间为$[min(id[x],id[y]),max(id[x],id[y])]$;
每次移动x点的时候,操作区间为$[id[top[x]],id[x]]$(注意这里左边界不是$id[f[top[x]]]$,因为这个点将在下次被计算)

代码只需要在LCA代码的基础上稍加修改就可以了:

1
2
3
4
5
6
7
8
9
10
11
12
void mod_path(int x,int y,int v)
{
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]]) swap(x,y);
t.add(id[top[x]],id[x]+1,v);//由于个人习惯,我的线段树操作区间是左闭右开区间,因此+1
//实际的方法参数会更多,这里忽略了次要矛盾,只突出了主要矛盾:操作区间和增加的值
x=f[top[x]];
}
t.add(min(id[x],id[y]),max(id[x],id[y])+1,v);
return;
}

同样是很简洁的代码,依然轻松的完成了任务.

查询节点x到节点y的最短路径上的所有节点/边的权值之和

思路完全同上,只是将方法从修改变为区间求和,设置一个临时变量累加,最后返回.

注意:如果有要求千万不要忘记取余,否则请估计结果大小开足够大的变量避免溢出.

代码只需要简单修改上面的片段就可以了.

1
2
3
4
5
6
7
8
9
10
11
12
int cal_path(int x,int y)
{
int ans=0;
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]]) swap(x,y);
ans+=t.cal(id[top[x]],id[x]+1);
x=f[top[x]];
}
ans+=t.cal(min(id[x],id[y]),max(id[x],id[y])+1);
return ans;
}

依旧简洁.

如何进行树剖

现在,我们已经看到了树剖所得到的结果能够正确的工作,帮助我们高效的完成之前提到的几种操作.现在,是时候考虑如何计算这些辅助数组的值了.我们同样分为几步考虑.

输入/建树

一般来讲,树的输入有两种:给出所有边的信息以及根节点的序号,或是给出根节点序号和f数组.无论对于哪一种情况,我们需要进行一次DFS.在这次DFS中,我们可以完成对f,size,dep,hson和head数组的初始化.

我们从根节点开始,对于每一个访问到的节点(记为t),标记t为已访问,将所有与其有边相连的未访问节点(记为to)的父节点设为t(若是第二种情况则可以省略这一步),并将to加入t的head集合中,更新to的dep的值,然后递归的以to为当前节点,继续操作,并在回溯时更新t的size和hson的值.下面是代码,更详细的解释将在代码中以注释的形式进行.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void link_constructor(int t)
{
a[t].size=1;//以当前节点为根的子树中目前只已知1个节点
visited[t]=1;//标记为已访问防止重复访问(死循环)
//这里使用了链表,其细节将在下文出现
edge* tar=temp[t];//temp用于临时存储边(适用于第一种情况),在输入时完成初始化
while(tar!=NULL)//直到不再有与当前节点有边相连的节点为止
{
edge* tt=tar->next;//由于之后可能会修改tar指向的结构体中的next指针,预先存储其指向的地址
if(!visited[tar->to])
{
a[tar->to].f=t;//设置父节点
a[tar->to].dep=a[t].dep+1;//设置深度:比父节点深1层
link_constructor(tar->to);//递归调用,先完成子节点的构建,以便更新当前节点的值
if(a[t].hson==0 || a[a[t].hson].size<a[tar->to].size) a[t].hson=tar->id;//若当前节点还没有重子节点或是重子节点不够重,进行更新
a[t].size+=a[tar->to].size;//更新当前节点的size,加上以子节点作为根的子树的size
tar->next=a[t].head;
a[t].head=tar;//将子节点加入集合
}
tar=tt;//查看下一个与当前节点有边相连的节点
}
return;
}

代码同样不长,现在,我们已经完成了f,size,dep,hson的计算,并删除了重边,完成了所有节点的子节点集合.

分割树

虽然我们首先进行了一次DFS,但是不幸的是,由于不能预先确定重子节点,我们并不能在这一次DFS中确定重链,也不能给节点编号.因此我们再进行一次DFS.在这一次DFS中,我们就可以利用上一次DFS中得到的重子节点的数据给节点依照我们规定的原则编号,并确定重链,初始化每个节点的top值.同样,更详细的将在代码中说明.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int Index=0;//用于编号
void split_constructor(int t)
{
//有关初始化的细节将在下文出现
id[t]=++Index;//编号
if(hson[t])//如果有重子节点
{
top[hson[t]]=top[t];//显然重子节点和其父节点在同一条树链上,拥有共同的链顶
split_constructor(hson[t]);//优先访问重子节点
}
edge* tar=head[t];
while(tar!=NULL)
{
if(tar->to!=hson[t])//注意不能重复访问节点
{
top[tar->to]=tar-to;//与父节点不在同一树链上,自己作为自己所在的树链的链顶
split_constructor(tar->to);
}
tar=tar->next;
}
return;
}

在这一次DFS中,我们按照之前确定的顺序,利用上一次DFS得到的信息,成功的将节点进行了编号,并且确定了各个节点的top值.这样就完成了对树的分割.

初始化线段树

最终的操作要有线段树完成,因此还要完成对线段树的初始化.由于所有操作的区间均由节点的编号决定,因此用于构造线段树的数组的下标将与节点编号对应.我们采用一种简单而直观的方法完成(或许并不优美):

1
2
3
4
5
6
int tempval[MAX];//临时数组,MAX是最大节点数
void sgtree_constructor(int n)//一共n个节点
{
for(int i=1;i<=n;i++) tempval[id[i]]=val[i];//将序号为i的节点的权值存储在临时数组下标为i的编号的位置
t.build(tempval,1,n+1);//调用线段树方法进行构造
}

这样,线段树也构造好了.

至此,各个部分均已完成,下面就只需要将这些部分串联在一起了.

总初始化函数

只要按照逻辑,依次执行第一次DFS,第二次DFS,线段树初始化就可以了.

1
2
3
4
5
6
7
8
9
10
void constructor(int n,int r)
{
f[r]=0;//根节点没有父节点
dep[r]=1;//根节点深度为1
link_constructor(r);//第一次DFS
top[r]=r;//根节点是自己所在的树链的链顶
split_constructor(r);//第二次DFS
sgtree_constructor(n);//初始化线段树
return;
}

至此,所有初始化已经完成,下面只需要正确的定义变量,正确的完成主函数的逻辑,按照要求处理输入的数据和指令并正确输出就可以了.下面,我们在实际问题中进行尝试.

例题

P3178 [HAOI2015]树上操作

事实上在洛谷是有树链剖分的模板题的,但是首先让我们从这个更简单一点的模板题开始吧(洛谷的模板题比这个要难).
这道题是一个纯粹的树剖,没有任何技巧,甚至不需要进行两个点的向上移动操作(一股清流),纯粹是练习逻辑的.那么直接上就好了,像我这样写代码奇丑的人代码量都还算可以.

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
214
215
#include<cstdio>
#include<algorithm>
using namespace std;
const int MAX=100010;

template<typename T>
struct sgtree
{
private:
T tree[MAX<<2];
T change[MAX<<2];

void updata(int t)
{
tree[t]=tree[t<<1]+tree[t<<1|1];
return;
}

void pushdown(int t,int l,int r)
{
if(!change[t]) return;
int t1=t<<1;
int t2=t<<1|1;
int m=(l+r)>>1;
tree[t1]+=change[t]*(m-l);
tree[t2]+=change[t]*(r-m);
change[t1]+=change[t];
change[t2]+=change[t];
change[t]=0;
return;
}

public:
void build(T a[],int l,int r,int t)
{
if(l==r-1) tree[t]=a[l];
else{
int m=(l+r)>>1;
build(a,l,m,t<<1);
build(a,m,r,t<<1|1);
updata(t);
}
return;
}

void add(int t,int l,int r,int low,int high,T v)
{
if(low<=l && r<=high){
tree[t]+=v*(r-l);
change[t]+=v;
}else{
pushdown(t,l,r);
int m=(l+r)>>1;
if(low<m) add(t<<1,l,m,low,high,v);
if(m<high) add(t<<1|1,m,r,low,high,v);
updata(t);
}
return;
}

T cal(int t,int l,int r,int low,int high)
{
if(low<=l && r<=high) return tree[t];
pushdown(t,l,r);
int m=(l+r)>>1;
T ans=0;
if(low<m) ans+=cal(t<<1,l,m,low,high);
if(m<high) ans+=cal(t<<1|1,m,r,low,high);
return ans;
}
};
sgtree<long long> sgt;

struct edge
{
int to;
edge* next;

edge()
{
to=0;
next=NULL;
}
};
edge e[MAX<<1];

int n;
long long val[MAX];
long long tempval[MAX];
int f[MAX];
int top[MAX];
int id[MAX];
int dep[MAX];
int hson[MAX];
int size[MAX];
bool visited[MAX];
edge* temp[MAX];
edge* head[MAX];

int Index=0;
int coun=0;

void add_edge(int x,int y)
{
e[coun].to=y;
e[coun].next=temp[x];
temp[x]=&e[coun++];
return;
}

void tree_con(int t)
{
visited[t]=1;
size[t]=1;

edge* tar=temp[t];
while(tar!=NULL)
{
edge* n=tar->next;
int& to=tar->to;
if(!visited[to])
{
f[to]=t;
dep[to]=dep[t]+1;
tree_con(to);
if(!hson[t] || size[hson[t]]<size[to]) hson[t]=to;
size[t]+=size[to];
tar->next=head[t];
head[t]=tar;
}
tar=n;
}
return;
}

void split_con(int t)
{
id[t]=++Index;

if(hson[t])
{
top[hson[t]]=top[t];
split_con(hson[t]);
}

edge* tar=head[t];
while(tar!=NULL)
{
int& to=tar->to;
if(to!=hson[t])
{
top[to]=to;
split_con(to);
}
tar=tar->next;
}
return;
}

void sgtree_con(void)
{
for(int i=1;i<=n;i++) tempval[id[i]]=val[i];
sgt.build(tempval,1,n+1,1);
return;
}

void constructor(int r)
{
tree_con(r);
top[r]=r;
split_con(r);
sgtree_con();
return;
}

long long cal_path(int x)
{
long long ans=0;
while(top[x]!=1)
{
ans+=sgt.cal(1,1,n+1,id[top[x]],id[x]+1);
x=f[top[x]];
}
ans+=sgt.cal(1,1,n+1,1,id[x]+1);
return ans;
}

int main()
{
int m,x,y,flag;
long long a;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%lld",val+i);
for(int i=1;i<n;i++)
{
scanf("%d%d",&x,&y);
add_edge(x,y);
add_edge(y,x);
}
constructor(1);
for(int i=1;i<=m;i++)
{
scanf("%d%d",&flag,&x);
if(flag==1){
scanf("%lld",&a);
sgt.add(1,1,n+1,id[x],id[x]+1,a);
}else if(flag==2){
scanf("%lld",&a);
sgt.add(1,1,n+1,id[x],id[x]+size[x],a);
}else if(flag==3){
printf("%lld\n",cal_path(x));
}
}
return 0;
}

P3379 【模板】最近公共祖先(LCA)

是的,是时候报复这道题了!之前能卡我的常数,看看这回用新的方法它还能不能卡住我!

这同样是树链剖分的删减版,虽然需要进行两点上移的操作,但是由于不需要计算权值,我们不需要构造线段树,也不需要为节点编号,只需要正确的top数组就可以AC这道题.因此,代码同样不长(虽然不长,但看起来依然很丑).

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
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAX=500010;

struct edge
{
int to;
edge* next;

edge()
{
to=0;
next=NULL;
}
};
edge e[MAX<<1];
edge* temp[MAX];
edge* head[MAX];
int f[MAX];
int next[MAX];
int size[MAX];
int dep[MAX];
int top[MAX];
int id[MAX];
bool visited[MAX];
int ecount=0;

void dfs(int t)
{
size[t]=1;
next[t]=0;

edge* tar=temp[t];
while(tar!=NULL)
{
edge* nn=tar->next;
if(!visited[tar->to])
{
dep[tar->to]=dep[t]+1;
visited[tar->to]=1;
f[tar->to]=t;
dfs(tar->to);
size[t]+=size[tar->to];
if(!next[t] || size[next[t]]<size[tar->to]) next[t]=tar->to;
tar->next=head[t];
head[t]=tar;
}
tar=nn;
}
return;
}

void split(int t)
{
if(next[t]!=0)
{
id[next[t]]=++ecount;
top[next[t]]=top[t];
split(next[t]);
}

edge* tar=head[t];
while(tar!=NULL)
{
if(tar->to!=next[t])
{
id[tar->to]=++ecount;
top[tar->to]=tar->to;
split(tar->to);
}
tar=tar->next;
}
return;
}

void build_tree(int s)
{
dep[s]=1;
visited[s]=1;
f[s]=0;
dfs(s);
return;
}

void init_split(int s)
{
id[s]=0;
top[s]=s;
split(s);
}

void total_init(int s)
{
build_tree(s);
init_split(s);
return;
}

int lca(int a,int b)
{
while(top[a]!=top[b])
{
if(dep[top[a]]<dep[top[b]]) swap(a,b);
a=f[top[a]];
}
return dep[a]>dep[b]?b:a;
}

int main()
{
int n,x,y,s,m;
scanf("%d%d%d",&n,&m,&s);
for(int i=0;i<n-1;i++)
{
scanf("%d%d",&x,&y);
e[i<<1].to=y;
e[i<<1].next=temp[x];
temp[x]=&e[i<<1];
e[i<<1|1].to=x;
e[i<<1|1].next=temp[y];
temp[y]=&e[i<<1|1];
}
total_init(s);
for(int i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
printf("%d\n",lca(x,y));
}
return 0;
}

这样就不会再被这道题卡常数了(虽然和没有使用vector有关,但实际上这种方法依然比使用了同样存储方式的倍增快近300ms).

P3384 【模板】树链剖分

终于来到了这里.我们已经在之前的两道例题中分别测试了树剖算法的一部分功能,而现在我们要将所有功能组合在一起,用完整版的树剖A掉这道题(“A上去就赢啦!”).

其实依然很简单,只要将所有功能放进去,写好主函数就已经成功了.(因为代码量变大了,所以代码更丑了)

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
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
#include<cstdio>
#include<algorithm>
using namespace std;
const int MAX=100010;
int count_edge=0;
int Index=0;
int n,pp;
bool visited[MAX];

template<typename T>
struct sgtree
{
private:
T tree[MAX<<2];
T change[MAX<<2];
T p;

void updata(int t)
{
tree[t]=(tree[t<<1]+tree[t<<1|1])%p;
return;
}

void pushdown(int t,int l,int r)
{
if(!change[t]) return;
int t1=t<<1;
int t2=t<<1|1;
int m=(l+r)>>1;
tree[t1]=(tree[t1]+change[t]*(m-l))%p;
tree[t2]=(tree[t2]+change[t]*(r-m))%p;
change[t1]=(change[t1]+change[t])%p;
change[t2]=(change[t2]+change[t])%p;
change[t]=0;
return;
}

public:
void init(T mo)
{
p=mo;
return;
}

void build(T a[],int l,int r,int t)
{
if(l==r-1) tree[t]=a[l]%p;
else{
int m=(l+r)>>1;
build(a,l,m,t<<1);
build(a,m,r,t<<1|1);
updata(t);
}
return;
}

void add(int t,int l,int r,int low,int high,T v)
{
if(low<=l && r<=high){
tree[t]=(tree[t]+v*(r-l))%p;
change[t]=(change[t]+v)%p;
}else{
pushdown(t,l,r);
int m=(l+r)>>1;
if(low<m) add(t<<1,l,m,low,high,v);
if(m<high) add(t<<1|1,m,r,low,high,v);
updata(t);
}
return;
}

T cal(int t,int l,int r,int low,int high)
{
if(low<=l && r<=high) return tree[t]%p;
pushdown(t,l,r);
int m=(l+r)>>1;
T ans=0;
if(low<m) ans+=cal(t<<1,l,m,low,high);
if(m<high) ans+=cal(t<<1|1,m,r,low,high);
return ans;
}
};
sgtree<int> sgt;

struct edge
{
int id;
edge* next;

edge()
{
id=0;
next=NULL;
}
}e[MAX<<1];

edge* temp[MAX];

struct node
{
int id;
int f;
int hson;
int val;
int top;
int dep;
int size;
edge* head;

node()
{
id=0;
f=0;
hson=0;
val=0;
top=0;
dep=0;
size=0;
head=NULL;
}
}a[MAX];

int tempval[MAX];

void link_constructor(int t)
{
a[t].size=1;
visited[t]=1;

edge* tar=temp[t];
while(tar!=NULL)
{
edge* tt=tar->next;
if(!visited[tar->id])
{
a[tar->id].f=t;
a[tar->id].dep=a[t].dep+1;
link_constructor(tar->id);
if(a[t].hson==0 || a[a[t].hson].size<a[tar->id].size) a[t].hson=tar->id;
a[t].size+=a[tar->id].size;
tar->next=a[t].head;
a[t].head=tar;
}
tar=tt;
}
return;
}

void split_constructor(int t)
{
a[t].id=++Index;
if(a[t].hson)
{
a[a[t].hson].top=a[t].top;
split_constructor(a[t].hson);
}

edge* tar=a[t].head;
while(tar!=NULL)
{
if(tar->id!=a[t].hson)
{
a[tar->id].top=tar->id;
split_constructor(tar->id);
}
tar=tar->next;
}
return;
}

void sgtree_constructor(int p)
{
sgt.init(p);
for(int i=1;i<=n;i++) tempval[a[i].id]=a[i].val;
sgt.build(tempval,1,n+1,1);
return;
}

void major_constructor(int r,int p)
{
a[r].dep=1;
link_constructor(r);
a[r].top=r;
split_constructor(r);
sgtree_constructor(p);
return;
}

void mod_xtoy(int x,int y,int v)
{
while(a[x].top!=a[y].top)
{
if(a[a[x].top].dep<a[a[y].top].dep) swap(x,y);
sgt.add(1,1,n+1,a[a[x].top].id,a[x].id+1,v);
x=a[a[x].top].f;
}
sgt.add(1,1,n+1,min(a[x].id,a[y].id),max(a[x].id,a[y].id)+1,v);
return;
}

int cal_xtoy(int x,int y)
{
int ans=0;
while(a[x].top!=a[y].top)
{
if(a[a[x].top].dep<a[a[y].top].dep) swap(x,y);
ans=(ans+sgt.cal(1,1,n+1,a[a[x].top].id,a[x].id+1))%pp;
x=a[a[x].top].f;
}
ans=(ans+sgt.cal(1,1,n+1,min(a[x].id,a[y].id),max(a[x].id,a[y].id)+1))%pp;
return ans;
}

int main()
{
int m,r,x,y;
scanf("%d%d%d%d",&n,&m,&r,&pp);
for(int i=1;i<=n;i++) scanf("%d",&a[i].val);
for(int i=1;i<n;i++)
{
scanf("%d%d",&x,&y);
e[count_edge].id=y;
e[count_edge].next=temp[x];
temp[x]=&e[count_edge++];

e[count_edge].id=x;
e[count_edge].next=temp[y];
temp[y]=&e[count_edge++];
}

major_constructor(r,pp);

int flag,z;
for(int i=1;i<=m;i++)
{
scanf("%d%d",&flag,&x);
if(flag==4) printf("%d\n",sgt.cal(1,1,n+1,a[x].id,a[x].id+a[x].size)%pp);
else if(flag==3){
scanf("%d",&z);
sgt.add(1,1,n+1,a[x].id,a[x].id+a[x].size,z);
}else if(flag==2){
scanf("%d",&y);
printf("%d\n",cal_xtoy(x,y)%pp);
}else{
scanf("%d%d",&y,&z);
mod_xtoy(x,y,z);
}
}
return 0;
}

A掉了这道题,就可以说是掌握了树剖的一些皮毛了.下面,再去洛谷寻找带有树链剖分标签的题,开始虐题(被题虐)吧.

后记

其实树链剖分本身并没有很难.它的逻辑很清晰,过程也极其简单:DFS1,DFS2,再写好线段树,基本就完成了.而难的地方是它衍生出来的花样.如果能够正确的看出来哪里可以用树剖解决,剩下的问题就好解决了.

我是一棵蒟蒻,如果有幸有大犇路过发现我哪里理解的不对,出现了偏差,还请大犇使劲的喷,那也是对我的帮助.谢谢.


本文标题:树链剖分学习笔记

文章作者:Snake

发布时间:2018年03月25日 - 16:03

最后更新:2018年04月28日 - 20:04

原始链接:https://snake.moe/2018/03/25/树链剖分学习笔记/

许可协议: 署名-非商业性使用-相同方式共享 4.0 国际 转载请保留原文链接及作者。