UOJ Logo liu_cheng_ao的博客

博客

一种基于错误的寻找重心方法的点分治的复杂度分析

2017-09-24 22:09:30 By liu_cheng_ao

我们知道,通常的点分治方法都基于重心,删除重心后将每个连通块分别分治。正常情况下寻找重心需要做树DP,需要遍历两次树(即使从上一层传入点数,也得在上一层遍历一次),某些选手就用了一些黑科技:从上一层传入“本层中与上一层重心相连的点”(称为根,记作 $K$)的以“上一层的根”为根的子树大小作为本层总点数

听起来很拗口,实际上是这么回事:(图中 $K'$ 表示本层的根,$K$ 表示上一层的根)

TR1.png

可以明显发现,当 $K$ 和 $K'$ 处于上一层重心 $O$ 的同一子树时,传入的点数是错误的。

这是否会对时间复杂度造成影响呢?

这与找重心的方式有关。我们讨论两种最常见的找法:

法1

从本层的根开始深度优先遍历,并同时计算出子树大小,以第一个所有子树大小不超过 $\frac{n}{2}$ 的为重心。

结论:算法错误

传入的点数值为 $n$。

可以举出反例:考虑这样一棵树:由重心和端点与之相连的三条长 $\frac{n-1}{3}$ 的链组成。初始的根位于某个叶子处。

第一层分治,传入到根所在链的大小为 $\frac{2n+4}{3}\geq 2\cdot\frac{n-1}{3}$,因而任何点都符合条件。按照深度优先顺序,这次找的“重心”是第一层的根。

第二层分治,传入到根所在链的大小为 $2<\frac{1}{2}\cdot(\frac{n-1}{3}-1)$(当 $n\geq 16$ 时)。这时不存在符合条件的点,分治无法进行,算法错误

法2

从本层的根开始深度优先遍历,并同时计算出子树大小,将传入值与以自身为根子树大小之差作为向本层根方向的子树大小,再取最大子树最小的点为重心。

结论:算法正确,递归层数 $O(\log n)$,访问节点的总次数 $O(n\log n)$。

我们来分析时间复杂度:

我们将分治结构稍作改变,只考虑输入点数等于实际点数的问题。显然当点数为 $1$ 时访问节点数 $O(1)$。

初始问题是符合条件的。现在考虑把问题分解前处理一层产生的代价(包括递归但大小错误的部分):

TR2.png

由于只有本层的根所在的方向递归时会错误,因而只要考虑对于本层重心而言根所在子树即可。

考虑一个问题。设本层实际大小为 $n$,以 $O_1$ 为根时含 $K_1$ 子树的根为 $K_1'$(也有可能 $O_1=K_1$,这时没有出现错误,复杂度正确),以 $K_1$ 为根时子树 $O_1$ 的大小为 $y_1$,以 $K_1'$ 为根时 $K_1$ 所在子树大小为 $x_1$。(均指实际大小)

解决本层的访问节点数为 $O(n)$。现在考虑递归到 $K'$ 的错误部分。该部分的实际点数为 $n-y_1$,传入点数为 $n-x_1$。设该部分处理时与上一层对应的部分用层数下标表示。以此类推直到 $K_i=O_i$ 为止。这一系列问题访问的总点数即为问题处理的代价。

运用归纳法,我们可以知道每一次的实际点数 $N_i$ 分别为 $n,n-y_1,n-y_1-y_2,...,n-\sum_{i=1}^{n-1}y_i$,传入点数 $N'_i$ 分别为 $n,n-y_1,n-x_1-y_2,...,n-\sum_{i=1}^{n-2}x_i-y_{i-1}$。

下面证明 $x_i \leq y_i$。使用归纳法,设对于 $j < i$ 该结论均成立(由重心显然对于第 $1$ 层成立)。实际上,若 $x_i > y_i$ 则对“重心”$O_i$ 而言包含 $K_i$ 的子树为最大子树,并且由于 $x_{i-1} \leq y_{i-1}$,本层的传入点数不小于实际点数。这样,用传入点数减去子树大小算出的点数不小于 $x_i$。故该算法计算出的 $O$ 的最大子树必为 $K_i'$ 且计算出的大小不小于 $x_i$。对 $K_i'$ 而言,除 $O_i$ 外的各子树大小计算值均小于其作为 $O_i$ 子树的计算值。又 $y_i< x_i$,故子树 $O_i$ 也小于该值。这样 $K_i'$ 计算出的最大子树严格小于 $O_i$ 的,与重心的计算定义矛盾。

更进一步地,我们可以证明 $y_i\geq \frac{1}{2}N_i$。证明方法类似:假设 $y_i<\frac{1}{2}N_i$,同上可证其最大子树必为 $K_i'$ 且计算的大小不小于其实际值,$N_i-y_i > y_i$。则对于 $K_i$ 而言,也可以用类似上一段的方法证明其计算出的最大子树严格小于 $O_i$,与重心的计算定义矛盾。

故有 $N_{i+1}\leq \frac{1}{2}N_i$。由于第 $i$ 层的访问点数为 $O(N_i)$,一个规模为 $n$ 的问题处理总点数满足 $T(n)=T(\frac{n}{2})+O(n)$,解得 $T(n)=O(n)$,且这部分递归层数 $O(\log n)$。

故分治时处理一个问题的时间为 $O(n)$。并且其分解出的子问题互不相交且都是正确方法的某个子问题的子集,故递归层数和子问题的时间复杂度不高于一般点分治。证毕。

评论

jjikkollp
orz
matthew99
第一段就看不懂
scallop
说的太好了,看到很多人这么写。
uniqriv
orz
dtcxzyw
orz
yw_Judge
讲的好迷啊,但是讲的很好 【雾
920848348
特创号来评论: 对于大部分点分治的代码中,不能直接size=sz【v】,否则会导致后面的重心求错(可以用下面的样例试一下,然后输出重心节点看一下,你会发现从 6->3 这一大块的重心应该是 2 ,而代码输出是 1 )原因在于: 由于一开始从 点 1 开始找整棵树的重心,此时的 sz【u】表示的仅仅是以 1 为根结点的树中,u 的子树大小。那么现在重心 root 找到了,那么从这整棵树的重心 root 开始深搜时,若有边 root->v ,而此时的 sz【v】的值并不是以 v 为根的子树的大小(这个子树当然不包括父亲 root 那一块)。具体为什么,这里给一组样例,大家可以在图中画一下。 此样例的对应题目为 洛谷P3806 11 1 6 7 1 6 8 1 7 9 1 7 10 1 8 11 1 1 2 1 1 3 1 2 4 1 2 5 1 3 6 1 2
920848348
然后我们一步一步来: 先从 1 开始 dfs ,统计 sz【】数组,此时很清晰的知道 sz【3】= 7 ,因为是以 1 为根深搜的。 很明显,一开始这整棵树的重心是 6 号节点,那么接下来,我们可以发现: 当从点 6 开始 dfs 时,有 6->3 这条边,那么按理来说,size=sz【3】,此时size 表示的是以 3 为根的子树的大小,可看图上明明是 5 啊(在点 3 的左边,不包含点 6 那边)。可是此时的 sz【3】 为 7 ,而并非是 5 。这是由于选定的深搜节点不同,统计的不同而导致的。sz【3】的正确值理应来自于从 点 6 开始深搜的值。 故我们可以得出结论,用 getroot(1,0) 找到整棵树的重心之后,再来一次 getroot(root,0),来确定以重心为根结点时的 sz【】 数组。这下就可以直接 size=sz【v】了。
huangzirui
@

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。