RainAir
My OI Blog
RainAir
点分治初探

点分治是什么:
首先选取一个点将无根树转为有根树,再递归处理每一棵以根节点的儿子为根的子树。
这样得到的分治结构有何用处?
通俗地讲,对任一个点,树的任一条路径要么经过这个点,要么不经过这个点,在这个点的子树里面。这对于树路径的计数等问题能够更容易的解决。
我们先详细介绍如何点分治,再来继续考虑使用。
考虑到我们每一次选择分治中心的时候,我们希望选出的这个根分出的子树的大小都尽量的小,我们可以选择使用这棵树的重心。
大致算法流程:
1. 求出当前树的重心,钦定重心为根
2. 统计当前树的答案
3. 对与当前树相邻的,未成为任何一棵树的重心的节点执行第一步。

注意到树的重心有一个性质:树的重心每棵子树的大小一定小于等于 $\frac{n}{2}$,也就说明了每一次分治过程都会减少至少一半的问题规模,所以时间复杂度是优秀的一个 $log$。
接下来我们看一道简单的经典例题:
POJ1741
给出一棵边权树,询问有多少对点的距离小于等于 $k$。
$2 \leq n \leq 10000,k \leq 2^{31}$。
我们考虑每一次点分治的时候对于分治重心求答案,以 $v$ 为根,统计所有经过 $v$ 的路径。
我们可以对于每一个点,求出到根的路径长度,设为 $dis$,这样我们就是求满足 $dis_x + dis_y \leq k$ ,且 $x$ 和 $y$ 不在以 $v$ 为根的同一个子树内的 $(x,y)$ 的方案数(同一个子树两点路径不一定经过根)。
我们首先不考虑子树限制,问题简化为给你一个 $dis$ 数组,求里面和小于等于 $k$ 的数对个数。我们可以对其排个序,然后双指针扫一遍统计答案。那我们首先不注意子树限制求出来一个答案,在单独减去每个子树对答案的贡献就可以了。
时间复杂度是 $O(nlog^2n)$ 的。

赞赏
知识共享许可协议
本文链接: https://blog.aor.sd.cn/archives/427
如文中无特殊声明,本文采用 CC BY-NC-SA 4.0 进行许可,转载请说明出处!
希望 CSP 不要翻车,希望省选不要翻车
https://secure.gravatar.com/avatar/97c17c68a1e55e11bb5558bc0f10cc0d?s=256&d=mm&r=g

RainAir

文章作者

一个OIer。

发表评论

textsms
account_circle
email

RainAir

点分治初探
点分治是什么: 首先选取一个点将无根树转为有根树,再递归处理每一棵以根节点的儿子为根的子树。 这样得到的分治结构有何用处? 通俗地讲,对任一个点,树的任一条路径要么经过这个点,…
扫描二维码继续阅读
2019-01-29
标签
近期评论