树链剖分(超详细!!!)

一、轻重边剖分的过程

使用两次dfs来实现。剖分过程中要计算如下7个值:

father[x]:x在树中的父亲

size[x]:x的子树结点数(子树大小)

dep[x]:x在树中的深度

son[x]:x的重儿子,即为重边

top[x]:x所在重路径的顶部结点(深度最小)

seg[x]:x在线段树中的位置(下标)

rev[x]:线段树中第x个位置对应的树中结点编号,即rev[seg[x]]=x

第一遍dfs时可以计算前四个值,第二遍dfs可以计算后三个值。而计算seg时,同一条重路径上的点需要按顺序排在连续的一段位置,也就是一段区间。

【代码实现】(预处理1):

树链剖分(超详细!!!)

【代码实现】(预处理2):

树链剖分(超详细!!!)

二、树上路径处理:

考虑将一条路径(u,v)拆分为若干条重路径:实际上就是寻找最近公共祖先的过程。考虑暴力的做法,我们会选择u,v中深度较大的点向上走一步,直到u=v。

现在有了重路径,由于我们记录了top和seg,因此我们不需要一步步走。假定top[u]和top[v]不同,那么他们的最近公共祖先可能在其中一条的重路径上,也可能在其他的重路径上,因为LCA显然不可能在top深度较大的那条重路径上,所以我们先处理top深度较大的。

首先我们找出u,v中top深度较大的点,假设是u,则我们可以直接跳到father[top[u]]处,且跳过的这一段,在线段树中是一段区间,若我们按照深度从小到大来存储点,则这段区间为:[seg[top[u]],seg[u]] 。 而当u,v的top相同时,说明它们走到了同一条重路径上了,这时它们之间的路径也是序列上的一段区间,且其中深度较小的那点是原路径的LCA。

【代码实现】(建树):

 树链剖分(超详细!!!)

【代码实现】(查询(u,v)路径信息):

树链剖分(超详细!!!)

直接上两道模板题吧(最近真的搞得心很累,博客也不想好好写了)



【例 1】树的统计(单点修改、区间查询)(信息学奥赛一本通 1560)

【题目描述】

一树上有 n 个节点,编号分别为 1到 n,每个节点都有一个权值 w。我们将以下面的形式来要求你对这棵树完成一些操作:

  1. CHANGE u t :把节点 u 权值改为 t;

  2. QMAX u v :询问点 u 到点 v 路径上的节点的最大权值;

  3. QSUM u v :询问点 u 到点 v 路径上的节点的权值和。 注意:从点 u 到点 v 路径上的节点包括 u 和 v 本身。

【输入】

第一行为一个数 n,表示节点个数; 接下来 n−1 行,每行两个整数 a,b,表示节点 a 与节点 b 之间有一条边相连; 接下来 n行,每行一个整数,第 i行的整数 wi表示节点 i 的权值; 接下来一行,为一个整数 q ,表示操作总数; 接下来 q行,每行一个操作,以 CHANGE u t 或 QMAX u v 或 QSUM u v的形式给出。

【输出】

对于每个 QMAX 或 QSUM 的操作,每行输出一个整数表示要求的结果。

【输入样例】

4

1 2

2 3

4 1

4 2 1 3

12

QMAX 3 4

QMAX 3 3

QMAX 3 2

QMAX 2 3

QSUM 3 4

QSUM 2 1

CHANGE 1 5

QMAX 3 4

CHANGE 3 6

QMAX 3 4

QMAX 2 4

QSUM 3 4

【输出样例】

4

1

2

2

10

6

5

6

5

16

 

贴上代码

树链剖分(超详细!!!)

树链剖分(超详细!!!)

树链剖分(超详细!!!)



「HAOI2015」树上操作(区间修改、区间查询)(信息学奥赛一本通 1561)

【题目描述】

有一棵点数为 N 的树,以点 1 为根且树有点权。然后有 M 个操作,分为三种:

  1. 把某个节点 x 的点权增加 a 。

  2. 把某个节点 x 为根的子树中所有点的点权都增加 a 。

  3. 询问某个节点 x 到根的路径中所有点的点权和。

【输入】

第一行包含两个整数 N,M。表示点数和操作数。 接下来一行 N 个整数,表示树中节点的初始权值。 接下来 N−1 行每行两个正整数 fr,to, 表示该树中存在一条边 (fr,to) 。 再接下来 M 行,每行分别表示一次操作。其中第一个数表示该操作的种类(1−3) ,之后接这个操作的参数(x 或者 x a)。

【输出】

对于每个询问操作,输出该询问的答案。答案之间用换行隔开。

【输入样例】

5 5

1 2 3 4 5

1 2

1 4

2 3

2 5

3 3

1 2 1

3 5

2 1 2

3 3

【输出样例】

6

9

13

 

代码++

树链剖分(超详细!!!)

树链剖分(超详细!!!)

树链剖分(超详细!!!)

 

 

 

 

 

 

 

 

 

上一篇:【模板】旋转卡壳求两凸包最短距离


下一篇:Java 中 如何将一个字符重复n遍