点分治

/ 0评 / 0

点分治

在开始树上点分治前,复习下树的直径,树的重点,以及深度,分治小知识。

树的直径

两遍$dfs()$,第一次求出直径的一个端点,第二次求出以该端点为根的最长路,即为直径。

树的重心

在树中找到一个点,使其所有的子树中最大的子树含有的节点是最少的。

POJ 1655 模板题

题意:求出树的平衡因子balance即确定重心后最大子树规模-1,注意输出重心小的优先。

树的点分治

一种高效的用来解决树上的路径问题的算法思想

以树的重心为根转换无根树为有根树,这样可以保证分而治之的子树规模相当,且有任何一颗子树的大小都不超过原来树大小的一半。

最坏情况下树会退化成一条链普通枚举要上到$O(n^2+n)$

#POJ 1741 Tree

题意:给出一棵树,问有多少$pair(u,v)$使得$dis(u,v)\le k$

暴力复杂度$O(n^2)$

分治思想:联想算法导论最大子数组的和,一条路径要么经过根节点,要么在根节点的一棵子树上,那么不妨对树“剖分”。

先求出经过根节点的路径数目,再对子树的根节点递归处理。
重点处理跨越根的路径。可套尺取,先求出到根节点的距离$dis[u]$,复杂度$O(n)$

排序$dis$问题转换成尺取,即在有序数组$dis$中找到数对满足和小于$k$,$O(n)$即可

但注意在降维后选择两点时会出现走重复路的情况也会被算在内,此时以孩子为实根,其父节点为虚根, dis[u]=e[i].w,减去在该虚根和实根下,路径长度小于k的对数。

#Code

发表评论

电子邮件地址不会被公开。 必填项已用*标注