• 周二. 7 月 16th, 2024

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

点分治笔记

admin

11 月 28, 2021

我们常用数据结构处理一些序列上的问题。这些问题的形式一般是给定序列的两个位置L和R,在区间[L,R]上执行查询和修改指令。如果给定的是一棵树,要求查询树上两个节点x和y路径的答案。点分治可以在一棵树上,对具有某些限定条件的路径静态地进行统计  

【例题】 Tree (Poj 1741)

    给定一棵有N个点的树,每条边都有一个权值。树上两个节点x与y之间的路径长度就是路径上各条边的权值之和。求长度不超过K的路径由多少条。

  

    本题树中的边是无向边,我们称之为无根树。也就是说,我们可以任意指定一个节点为根节点,而不影响问题的答案。

   若我们指定节点p为根,则对p而言,树上的路径可以分为两类:

    1.  经过根节点p

    2. 包含于p的某一颗子树中。

    根据点分治的思想, 对于第2类路径,显然可以把p的每颗子树作为子问题,递归进行处理。

   而对于第一类路径,可以从根节点p分成“x~p”与“p~y”两段。

  我们可以从p出发,对整棵树进行DFS,求出数组d,其中d[x]表示点x 到根节点p 的距离。 同时还可以求出数组b, 其中b【x】表示点x属于根节点p的那一颗子树,特别地,令b[p] = p。

  那么此时满足题目要求的第一类路径就是满足一下两个条件的点对(x,y)的个数:

    1.  b[x] != b[y]

    2. d[x] + d[y] <= k

  我们定义Calc(p)表示在以p为根的树中统计上述点对的个数(第一类路径的条数)。Calc (p)有两种常见的实现方式。 针对不同题目,二者各有优劣。

  方法一: 树上直接统计

  设p的子树为S1, S2, …, Sm

  对于Si中的每个节点x, 把在子树S1, S2, … Si-1 中的满足d[x] + d[y] <= k 的节点 y 的个数 直接累加到答案中即可。

  具体来说,可以建立一个树状数组,依次处理每一个子树Si。

    1. 对于Si中的每个节点x, 查询前缀和 ask(k – d[x]) ,即为所求的y的个数。

    2. 对于Si中的每个节点x,执行add(d[x], 1),表示与p距离为d[x]的节点增加了一个。

  按子树一颗一颗进行处理保证了b[x] != b[y], 查询前缀和保证了d[x] + d[y] <= k.

  需要注意的是,树状数组的范围和路径长度有关,这个范围远比N要大。而本题中不易进行离散化。一种解决方案是用平衡树代替树状数组。以保证O(NlogN)的复杂度,但是代码的复杂程度显著增加。所以本题更适合用下一种方法。

  方法二: 指针扫描树状数组。

发表回复