树上算法

Published: by Creative Commons Licence

  • Tags:

轻重链技术

轻重链技术,是指我们将树上的边分成两类,轻链和重链。一个结点的大小最大的子树,称为这个结点的重孩子(一个结点最多只有一个重孩子),与重孩子相连的边叫做轻边。

考虑从任意一个顶点向根结点走,没经过一条轻边,则子树大小至少翻倍,因此可以直接推出任意一个顶点到根结点路径上最多有$O(\log_2n)$条轻边。

又了上面的结论我们就可以实现很多算法。比如dsu on tree、轻重链剖分。

题目1:给定一颗前缀树,每条边上都标记一个小写字母。现在希望选择某个$p$,并将前缀树中所有长度大于等于$p$的字符串都删除掉第$p$个字符。之后重新构建前缀树,要求新的前缀树包含尽可能少的顶点。其中$n\leq 3\cdot 10^5$

考虑删除第$p$层的所有顶点带来的影响,我们需要合并删除的顶点下的子树。

具体实现就是我们进行DFS,对每个结点计算删除其所有孩子后可以得来的优化。我们将所有其它剩余的子树合并到重孩子的重孩子中去。可以发现每个结点每次合并到其余子树去(贡献1),对应孩子到父亲的路径中两条连续边其中至少一条边为轻边,很显然每个孩子最多产生贡献$O(\log_2n)$。

总的时间复杂度为$O(26n\log_2n)$,其中$26$来自于字符集。

一道CF题目

dsu on tree

树上DP有很多种形式,下面给出一个树上DP的题目:

n个结点,每个结点有一个颜色,要求我们计算每个结点作为根的子树中不同的颜色数目。

这个问题,你可以通过哈希表以及启发合并来实现,这样的时间复杂度就为$O(n\log_2{n})$。

当然由于哈希表的常数和消耗的空间会略大,你可以使用莫队算法,这样的时间复杂度为$O(n\sqrt{n})$。

还有一种就是使用一种树上启发合并的方式,其起源于Codeforce的一篇博客Sack (dsu on tree)。Dsu on tree算法适用于有根树的所有子树的DP。下面说一下流程:

首先我们要对有根树进行轻重链剖分。

之后我们对树进行深度优先搜索,计算DP值。计算DP值分成三步,对由轻链连接的子树递归调用当前过程,但是要清除它们带来的影响(我们会维护一个全局的数组,记录子树的状态,在这个问题中就是一个布尔数组,记录颜色是否出现,这里消除影响的意思是将数组恢复到对这些子树调用递归过程之前的状态)。之后我们对重链边连接的子树进行递归调用,但是保留它们的状态,并用在当前结点的状态计算上。之后分别对轻链连接的子树调用一次递归过程,但是这个过程既不是为了计算子树的DP,也不要求清除状态,但是要把原来的状态附加到现有的状态上。

因此我们可以将DFS分成两种,第一种我们称为动态规划流程,其目的是为了利用子树的状态计算当前结点的DP值,我们称为计算过程;第二种是不计算自己的DP值,而只是贡献自己的状态信息,我们称为贡献流程。

而我们会为每个结点调用一次计算流程,会为每条轻链连接的子树调用一次贡献流程。当然你可能会问,为什么不在计算流程中把计算结果保存下来呢,这样只需要合并一下,而不需要使用慢的多的贡献流程。原因是这样的,味为每个结点都保存状态,考虑所有的结点仅于根结点有一条连接的边,那么我们在计算跟结点的状态的同时,还需要保存(n-1)份状态信息,而每份状态信息的大小都是$|C|$,C是可能的颜色的集合。当然你会说我们可以使用哈希表来节省内存,但是使用哈希表的话性能会大幅度恶化,而且同样也会占用大量的空间,这样对于时间和空间限制比较严格的情况下是很难通过的。

下面聊聊时间复杂度。在我们上面的问题中,计算流程的时间复杂度为$O(n)$,而贡献流程,每个结点最多会参加与自己到根结点的路径上轻边数目相同次数的贡献流程(在任意一颗大小为$n$的树中,每条一个端点为根结点的路径最多有$\log_2{n}$个轻边),而每次参加的时间复杂度为$O(1)$,共$n$个结点,因此贡献流程的总时间复杂度为$O(n\log_2{n})$。轻重链剖分的时间复杂度为$O(n)$,因此总的时间复杂度为$O(n\log_2{n})$。

边分治

边分治类似于点分治,区别在于点分治找的是重心点,而边分治找的是重心边。

树T的重心边是指这样一条边e,使得删除e后得到的两个连通块大小的最大值最小,我们记作$effect(e)$。

由于对于菊花图,任何边得到的连通分块的大小都是1和n-1,因此边分治不能得到很好的效果。我们可以插入一些假的顶点,使得每个顶点下只挂两条边(不包括与父亲相连的边)。

现在在已知树中每个顶点的度都不超过3的前提下,我们证明假如e是树T的重心,且T的大小为n,那么$effect(e)\leq \frac{2}{3}n$。实际上假设e是树T的重心,连接两个顶点u、v。不妨认u所在连通块的大小大于$\frac{2}{3}n$。考虑到u至多还能连接两条边,因此至少有一条边e'的另外一端所在连通块的大小能达到$\frac{1}{3}n$。e'是比e更好的重心。

边分治的优势在于边连接的一定是父子,因此可以将树分成两部分,包含根的记作R,不含根的记作B。而R中任意顶点x,与B中所有顶点的LCA是相同的,因此可以提前计算并用于后面的处理。

边分树

考虑要处理这样的问题,有两棵树T1和T2,对于某个不同顶点对u、v,定义它们的距离为:

其中$dist_1$为第一颗树上的距离,$dist_2$是第二颗树上的距离。这个问题可以通过边分数来消除第一颗树上LCA带来的影响,之后为第二颗树建立虚树,可以消除第二颗树上LCA的影响,之后就成为一般的DFS统计最远顶对问题,时间复杂度是$O(n(\log_2n)^2)$。

可以用另外一种叫做边分树的技术来优化。我们为每个顶点额外维护一个二叉树,初始时只有一个顶点。在对第一个树进行边分治时,删除边重心后,会得到两个连通块,记作a、b。我们将a上的顶点二叉树深度最大的叶结点下加上一个左孩子,为b上顶点二叉树深度最大的叶结点下加上一个右孩子。完成了边分治后,每个顶点所对应的二叉树实际上都是一条弯曲的链表(长度为$O(\log_2n)$),之后我们在第二颗树上进行DP操作。对于每个顶点,当递归处理完一个子结点时,就将它的二叉树和自己的二叉树进行合并,合并的时候对于处于二叉树左右不同分支的顶点,可以统计其贡献。这样就能在$O(n\log_2n)$的时空复杂度下解决问题。

树上最远点对

命题1:如果树上边权非负,对于两个顶点集合A、B,设A中最远点对为$a_1,a_2$,而B中最远点对为$b_1,b_2$,那么在A、B合并后,其中最远点对一定可以从${a_1,a_2,b_1,b_2}$中得到。

命题2:如果树上边权非负,并定义树上距离为路径距离加上两点的点权,对于两个顶点集合A、B,设A中最远点对为$a_1,a_2$,而B中最远点对为$b_1,b_2$,那么在A、B合并后,其中最远点对一定可以从${a_1,a_2,b_1,b_2}$中得到。

命题3:如果树上边权非负,那么以任意顶点为根,从最深的顶点中选择一个顶点,这个顶点一定是某个树上直径的端点。

树上中点(边)

如果一颗树的直径为$D$。

如果$D$是偶数,那么树上一定存在一个顶点,到其它所有顶点的距离不超过$D/2$,这个顶点称为树的中点。

如果$D$是奇数,那么树上一定存在一条边,使得其它所有顶点到边的某一端的顶点的距离不超过$(D-1)/2$,这条边称为树的中边。

任意取一条树上直径,如果直径长度为偶数,那么直径中心的顶点就是树的中点,假如直径长度为奇数,那么直径中心的边就是树的中边。

如果树上有多个直径,那么树上所有直径都一定过中点(中边)。

最小子树统计

对于一株树$T=(V,E)$,对于任意$V$的子集$S$,包含$S$的顶点最少的子树的顶点数目记作$f(S)$。

要求:$\sum_{S\subset V}f(S)$

这个问题站在顶点的角度看,是很难解决的。但是如果站在边的角度看问题就很简单了,记$g(S)$表示包含$S$的顶点最少的子树中的边集。那么我们可以推出:

其中$[e\in g(S)]$为1,当且仅当$S$中包含从$T$中删除$e$后得到的两个子树中顶点至少一个。因此我们利用容斥,从所有可能的$V$的子集中删除仅覆盖$e$一侧顶点的集合数即可得到,记$L(x)$表示边左侧子树大小,$R(x)$表示边右侧子树大小,那么结果就是:

因此最终结果可以表示为:

这个可以通过dfs线性统计出来。

长链剖分

长链剖分可以用于解决一些树上与高度相关的DP问题。

长链剖分类似于dsu on tree。

首先我们要处理出一颗树中的长链。记Len(x)表示顶点x到以x为根的子树中最深的叶节点的距离。对于任意结点x,设y为x直接子结点中Len最大的(如果有多个最大,则仅选择其中一个),那么我们将x和y之间的边称为长边,由长边组成的路径称为长链。这样操作后,整颗树将包含若干条链,这些链没有公共顶点和公共边,并且每个结点唯一属于一条链。

性质1:由于没有公共边,所有长链的总长度不超过n。

性质2:顶点x的k级祖先y所在链的长度一定不小于k

证明:

如果x和y处于同一长链,很显然成立。

否则由于x在y的子树中,故Len(y)>=k,因此可知y所在长链一定不小于k。

在线查询树上某个结点的k级祖先

我们可以使用倍增算法找到每个顶点的所有2次幂祖先顶点。之后对于所有长链顶部结点x,为其创建两个两个大小为L=Len(x)-1的数组A、B,其中A保存x上面L个顶点,而B保存x沿着长链向下的L个顶点。之后还需要预先计算1~n中每个数的二进制最高位。上面的所有过程总的时间复杂度为$O(n\log_2n)$,空间复杂度为$O(n\log_2n)$。

之后对于诸如询问询问x的k级祖先,我们用倍增先找到x的$highestBit(k)$级祖先y,之后对于$k'=k-highestBit(k)$,可以推出$k'<highestBit(k)$,而我们由性质2得到y所在的长链的长度至少为$O(highestBit(k))$,因此我们可以直接利用y所在长链顶部顶点的A、B数组直接查表得到。

查询树上最长k边路径

为每个长链顶部顶点创建一个与其所在长链的长度相同的数组,这里总的空间复杂度为$O(n)$。

之后我们处理非顶部顶点x时,我们就复用顶部顶点的预分配的数组,第i个元素记录x子树中由i条边组成总权最大路径的总权。

首先我们先递归处理长边连接的顶点,之后和通过短边连接的顶点的数组合并。

由于只有长链顶部顶点会对父元素产生与其长度相同的贡献,因此时间复杂度为$O(n)$。

两棵树的换边问题

题型1:给定两颗均包含$n$个顶点的树,第一颗树的边的颜色都为白色,第二颗树的边的颜色都是黑色。现在要求我们每次从第一颗树删除一条白边,并从第二颗树删除一条黑边,并将删除的黑边加入到第一颗树中,要求每次操作完成后第一颗树依旧是树(连通无环)。重复上述操作只到第一颗树的边全为黑,第二颗树无边。要求输出每次删除的白边和黑边。

这个问题有一个构造算法:

  1. 如果树2不存在黑边,则退出,否则进入步骤2。
  2. 从树2中任意删除一条黑边,边记作$b$。
  3. 将$b$加入树1,此时树1会出现一个唯一的环。出现的环中一定有白边(否则黑边成环意味着树2初始时一定有环),任意选择一条白边$w$,并移除。
  4. 回到步骤1。

很显然上面的算法是正确的,我们可以用LCT实现这个算法,时间复杂度为$O(n\log_2n)$。

题型2:给定两颗均包含$n$个顶点的树,第一颗树的边的颜色都为白色,第二颗树的边的颜色都是黑色。现在要求我们计算白边和黑边的最大匹配,白边和黑边相连当且仅当我们从将树1的这条白边和树2的这条黑边交换,两颗树依旧是树(连通无环)。要求输出最大匹配以及配对的白边和黑边。

考虑对于树2中的任意一条边$e_2=(u,v)$,从树2中删除并加入树1后,树2出现两个连通块,而树1出现一个环。

命题1:此时树1中从$u$到$v$的唯一路径上一定有一条边$e_1$,满足将$e_1$加入树2后树2连通。

证明:考虑从$u$到$v$的唯一路径,路径的两个端点在树2中处于不同的连通分块,因此,我们一定可以找到路径上一对相邻的顶点(又是间隙二分哦),顶点在树2中处于不同的连通分块。找到了这两个顶点,我们也就确定了$e_1$。

利用命题1,我们可以每次选择一条黑边,同时找到对应的白边。但是这时候问题出现了,同一条白边可能被多条黑边所匹配。解决方法就是我们每次找一条黑边,再在树1中找到一条可交换的白边,达成匹配后,我们将黑边从树2删除,并用白边代替它(但是我们始终保持树1不变)。这样我们能保证下一条树2中的黑边还能在树1中找到可以交换的白边,且这条白边一定没有被匹配过(否则再次被加入树2,出现了重边,此时一定有环)。

上面的流程保证了我们最大匹配一定是完美匹配。

暴力的做法就是$O(n^2)$。但是我们发现每次树1是不变的,因此我们可以提前在树1上计算倍增,之后在树1上查询路径的时候就可以二分路径找到端点属于不同连通块的边了。但是由于树2会不断变动,要维护它的连通关系,我们可以使用LCT或则动态图判连通算法,这样总的时间复杂度均为$O(n(\log_2n)^2)$。

但是这里有一个额外的技巧,我们发现每次选择一个端点为叶子的黑边,我们可以非常简单的判断连通性。对应的,当加入白边到树2中时,考虑到白边永远不会再被删除,因此我们可以保证白边的两个端点之后将一直保持连通,我们可以将两个顶点合并(合并并查集)。于是乎我们就提供了一个$O(1)$维护连通性的算法,总的时间复杂度降低到$O(n\log_2n)$。

Codeforces上有一道原题

一类树上分割问题

题目1:给定一颗有$n$个顶点的树,其中$n\leq 10^5$,之后定义$f(i)$表示将树分解为若干个连通块,问最多能分解出多少个大小正好为$i$的连通块。要求输出$f(1),f(2),\ldots,f(n)$

这是Blogewoosh #3提出的问题和解法,我这里只是搬运而已。但是一部分内容是我自己的,与原文可能有些出入。

我们可以定义另外一个函数,记$g(i)$表示将树分解为若干个连通块,其中最多能分解出来大小至少为$i$的连通块数目。很显然$g(i)\geq f(i)$,但是由于任意大于等于$i$的连通块都可以从中切割出一个大小正好为$i$的连通块,因此$f(i)\geq g(i)$。因此总结得出$f(i)=g(i)$,即$f=g$。

于是乎问题就变成了我们希望将树分解为大小至少为$i$的若干个连通块。

首先很显然,我们对树进行dfs,并且同时做出贪心选择,如果子树中未分配的顶点总数加上自己,大小大于等于$i$,那么我们将自己与父亲的连边删除并得到一个大小不小于$i$的新连通块。这是一种贪心做法。

现在我们来证明贪心的正确性,假如存在最优解,使得存在这样一个顶点,其与父亲的连边未删除,且子树中未分配的顶点数目加上自己不小于$i$,那么我们可以删除与父亲的连边(如果操作后父亲大小不足,我们可以舍弃父亲),这样绝对不会使得最优解劣化。因此我们证明了贪心的正确性。

于是乎我们就得到了一个$O(n^2)$的暴力做法。

现在让我们来优化一下,注意到不等式$f(i)\leq \lfloor \frac{n}{i}\rfloor$一定成立,因此当$i\geq \sqrt{n}$时,$f(i)$只可能有$\sqrt{n}$种取值。因此我们可以分两种情况处理,对于$i\leq \sqrt{n}$,我们可以暴力计算,这里花的时间为$n\sqrt{n}$,而对于$i>\sqrt{n}$,由于$f$是递减函数,因此一定存在一个区间$[l,r]$(可能为空)和某个数$x<\sqrt{n}$,使得$f(l)=f(r)=x$。我们可以用二分来加速计算。

上面的优化后的算法的时间复杂度为$O(n\sqrt{n}\log_2n)$,但是实际上我们可以选择暴力计算到$\sqrt{n\log_2n}$,这样真实的时间复杂度就会降低到$n\sqrt{n\log_2n}$。

上面提供了一种有通过可能性的算法。

下面我们再来讨论一种更快速的方式。

考虑当树是毛毛虫状的,即除了叶子结点外,其余顶点恰好形成一条路径(主干),这时候我们就可以用线段树维护它,之后对于块大小至少为$i$时,我们可以用最多$\frac{n}{i}$次二分法(在线段树上二分),找到树最多能切分为多少段,这样所需的时间复杂度为$O(\frac{n}{i}\log_2n)$。很显然,当$i$很小的时候,算法的速度反而变慢了,但是观察总的性能,我们会发现为$O(n(\log_2n)\sum_{i=1}^n\frac{1}{i})=O(n(\log_2n)^2)$,反而变快了有木有。

当然上面这个算法仅适用于毛毛虫状树。但是仔细思考普通树和毛毛虫状树区别是什么,实际上在贪心的过程中,毛毛虫状树我们只需要处理主干,但是普通树,如果存在另外一个分支大小超过$k$,那么我们必须同时处理这个分支。因此我们可以将所有大小超过$i$的分支从原来的树中分离出来,独立计算贡献,最后统计到结果中去。那么分支不会很多吗?不会多的,在要求连通块大小至少为$i$的前提下,一棵树的分支数最多为$\frac{n}{i}$,而总的流程中,最多存在$O(n\log_2n)$个分支。

因此到此我们就得到了整个算法。我们可以对树进行轻重链剖分,之后将每条重链放到线段树上进行维护。每当我们发现分支小于当前的要求的时候,我们就将分支合并回原本分出的位置。在线段树上我们可以维护动态规划,来支持二分操作。每次二分的时间复杂度为$O(\log_2n)$,而每次分支对主干的贡献也为$O(\log_2n)$,因此总共的时间复杂度为$O(n(\log_2n)^2)$。

树上路径统计问题

问题1:给定一株拥有$n$个顶点的树,每个顶点都有点权,要求回答$m$个请求,每个请求给定$u,v$,要求计算$u$到$v$的唯一路径上所有顶点的点权和

这个问题做法非常多。简单的就是动态树或者树链剖分。或者我们可以发现每条唯一路径都有一个深度最小的顶点$lca(u,v)$,所以问题也可以转换成差分。

时间复杂度最小可以优化到$O(n)$(利用线性计算LCA的技术)。

问题2:给定一株拥有$n$个顶点的树,每个顶点都有点权。给定一个数$m\leq 10^6$,要求回答树上存在多少条路径,满足路径上顶点的权重之和正好等于$m$,$(u,v)$和$(v,u)$认为是不同的路径,如果$v\neq u$

问题1中提出的解决路径统计的技术已经无法解决问题2了,因为它们只能支持逐路径查询,但是这里路径总共有$n^2$条。

首先我们可以先提前计算掉有多少个顶点的权重恰好等于$m$,而之后我们只需要考虑那些长度至少为2的路径有多少条即可。

一种最简单的方案就是树上DP,但是由于点权的范围可能比较大,因此我们不能以数组来存DP,而需要借助哈希表。而在计算某个顶点的贡献的时候,我们需要合并所有孩子的哈希表,这个可以借助启发式合并,总的时间复杂度为$O(n\log_2n)$,但是由于用了哈希表,因此常数较大。

第二种方式就是利用DSU on tree,这样做的好处就是可以摆脱哈希表的常数。在顶点继承重孩子的数据的时候,我们需要将所有数据的权重增加该顶点的权重,这里我们可以通过维护一个全局变量实现。总的时间复杂度为$O(n\log_2n)$,常数较小。

第三种方式就是利用重心剖分。我们每次都找到重心,并暴力统计经过重心的路径的贡献。在计算完重心后,递归处理重心下的所有子树。这样做的时间复杂度同样也是$O(n\log_2n)$,但是常数适中。

这三种方式各有优劣:

  1. 第一种方式好想好写好调,但是就是容易TLE或MLE。
  2. 第二种方式跑得快,就是必须要求顶点可以快速继承孩子的数据,使得只能在一些特殊问题中发挥作用。
  3. 第三种方式泛用性极强(不要求继承数据,每次都可以清空重来),但是代码篇幅会较大且容易写错,而且跑的也没第二种方式快。

问题3:给定一株拥有$n$个顶点的树,每个顶点都有点权。现在定义路径$(u,v)$上的顶点的权重分别为$x_1,x_2,\ldots,x_k$,定义$f(u,v)=\sum_{i=1}^k(k-i+1)x_i$,要求计算$f$的最大可能取值

首先我们来考虑如何计算$f(u,v)$,考虑路径中某两个相邻顶点对$(x,y)$,我们可以通过合并$(u,x)$和$(y,v)$的信息来得到$(u,v)$。简单的思路是$(y,v)$对$(u,v)$的贡献仅为$f(y,v)$和$(y,v)$长度,而$(u,x)$对$(u,v)$的贡献仅为$f(u,x)$与$(u,x)$上顶点的总权值。因此我们可以写出$f(u,v)=f(u,x)+f(y,v)+S(u,x)L(y,v)$,其中$S(u,x)$表示路径总权,而$L(y,v)$表示路径总长。

我们可以特殊的选取$x$为$lca(u,v)$,这样我们就能以动态规划的方式解决这个问题了。我们可以考虑按顺序处理子树,并用凸包技巧维护子树信息。

现在我们可以考虑问题2中提出的三种算法,看是否能用来解决这个问题。

首先如果我们使用树上DP的方式,那么每个顶点都需要处理整个子树的信息,这样时间复杂度就为$O(n^2\log_2n)$,还不如暴力。

如果我们使用DSU on tree技术,那么问题来了,如果继承重孩子的数据呢,因为我们必须修改凸包技巧中存储的一阶多项式。

现在考虑最后的重心剖分,你会发现由于每次都重新建立凸包技巧,因此我们不需要考虑如何继承的问题。因此重心剖分是可行的,总的时间复杂度为$O(n(\log_2n)^2)$。

提供CF原题

问题4:给定一个拥有$n$个顶点的树,每条边都有一个颜色(黑色或白色)。对于一条路径,称其为良好的,当且仅当路径中的黑边数$b$与白边数$w$满足$2w\geq b\land 2b\geq w$。现在要求统计所有$n^2$条路径中,有多少路径是良好的。其中$1\leq n\leq 10^5$

很显然只有一个顶点的路径永远是良好的,我们先不统计它们,最后结果加上$n$即可。

由于是所有路径的查询,因此很自然可以想到用点分治。找到树的重心,统计所有过重心的路径,并对重心下的子树递归处理。

现在剩下的问题是,我们如何处理判断过重心的路径是良好的。暴力当然是没有意义的(这和暴力就一样了),我们可以发现路径可以分成两部分,第一部分就是从某个子树到重心,另外一部分就是从重心到某颗子树。我们用$(x,y)$表示第一部分的路径,意思是拥有$x$条白边和$y$条黑边,同理用$(a,b)$表示第二部分的路径。现在我们可以发现两部分合成的路径是良好的,必须满足$2(a+x)\geq b+y$,我们稍加转换可以得到新的公式$2a-b\geq y-2x$,因此我们可以把路径第一部分的$y-2x$丢到BIT或其它RMQ结构中,这样在枚举第二部分时,可以$O(\log_2n)$统计有多少第一部分满足条件。当然仅仅满足这个条件还是不够的,还需要满足$(a+x)\leq 2(b+y)$。一个条件简单,两个条件就很麻烦了,但是注意到满足第一个条件的集合和满足第二个条件的集合的并集一定是全集,因此可以用简单的容斥进行处理。

记$A$为满足第一个条件的第一部分路径组成的集合,$B$为满足第二个条件的第一部分路径组成的集合,$S$为全集,我们要求的是:

对第二个条件也可以转换为$2b-a\geq x-2y$的形式,我们用同样的RMQ技术维护即可。

总的时间复杂度为$O(n(\log_n)^2)$。

提供一道题目

LCA算法及应用

在有根树中,两个顶点的LCA是指二者的所有公共祖先中深度最大的那个。

LCA的性质:

  • 两个顶点$u,v$的唯一路径一定经过它们的LCA,且它们的LCA是$u,v$路径上深度最小的顶点。

LCA算法的实现方式大概有以下几种:

  • 离线tarjan算法,时空复杂度为$O(n)$。
  • 树上倍增,预处理时空复杂度$O(n\log_2n)$,之后每个请求处理的时间复杂度为$O(\log_2n)$。
  • ST表+树上DFS序,预处理时空复杂度$O(n\log_2n)$,之后每个请求处理的时间复杂度为$O(1)$。
  • Schieber Vishkin算法,预处理时空复杂度$O(n)$,之后每个请求处理的时间复杂度为$O(1)$。
  • Link Cut Tree做法,允许换根和加边删边,预处理时间复杂度$O(n\log_2n)$,空间复杂度$O(n)$,之后每个请求处理的时间复杂度为$O(\log_2n)$。

LCA算法还可以用于解决下面一类问题:

  • 判断某个顶点$x$是否落在$u,v$的唯一路径上:首先$x$一定处在$lca(u,v)$子树内,且$x$一定是$u$或$v$的祖先。
  • 判断$x_1,y_1$的路径与$x_2,y_2$的路径是否有交点:两条路径假如有交点,记任意交点为$z$,很显然$z$一定是$x_1$或$y_1$的祖先,且$z$还是$x_2$或$y_2$的祖先。因此可以推出$lca(x_2,y_2)$一定是$x_1$或$y_1$的祖先,且$lca(x_1,y_1)$还是$x_2$或$y_2$的祖先。
  • 计算$u,v$的路径长度:长度为$depth(u)+depth(v)-2\cdot depth(lca(u,v))$

子树划分问题

题目:给定$n$个顶点构成的树,以及某个给定的正整数$k$,要求将树划分成若干个区域,每个区域中顶点数目都落在区间$[k,3k]$之间,或者报告无解。且我们需要为每个区域设置一个中心顶点,中心顶点可以不属于这个区域的任何顶点(但是它必须属于某个特定的区域),但是这个区域到自己的中心顶点所经过的路径上的所有顶点(除了最后一个)都需要属于这个区域(换句话说,如果中心顶点属于当前区域,那么当前区域连通)。

首先我们先证明如果树中拥有超过$k$个顶点,那么树一定能被划分。

设树的大小为$T$,当$k\leq T\leq 3k$的情况下,我们可以将整个子树作为一个连通块,即此时树能被正确划分。现在考虑$T>3k$的情况。我们可以这样做,首先找到树的重心,接下来分若干种情况讨论。

  • 如果重心的重孩子大小小于$k$,我们可以利用一种贪心算法,不断向当前构建的子集添加重心下的子树,直到子集大小超过$k$,就开始构建下一个子集,这些构建得到的子集的中心都是重心。现在可能最后构件的子集大小小于$k$,此时一定有构建好的某个大小范围为$[k,2k)$的区域,我们将当前区域以及根顶点全部加入这个区域中,很显然此时区域的大小范围为$[k,3k)$。
  • 如果重心的重孩子大小大于$k$,且所有大小小于$k$的子树大小之和不小于$k$,我们可以将所有大小大于等于$k$的孩子递归调用递归流程,并从重心上删除这些子树。最后我们重新对孩子调用点分治即可,很显然所有调用递归的子树规模都减少了至少一半。
  • 否则重心的重孩子大小大于$k$,且所有大小小于$k$的子树大小之和小于$k$,这里我们从所有大小不小于$k$的子树中,选择非重心的任意一个子树保留,其余大小不小于$k$的子树调用递归处理掉,最后递归处理剩下的子树。现在剩下的顶点数应该小于等于$T-\frac{T-b}{2}$,注意到$T>3k$,因此最多为原树大小的$\frac{2}{3}$。

上面的流程给出了一个分治的方案,且每次调用分治,子树的规模都至少缩小为原来的$\frac{2}{3}$。因此时间复杂度应该为$O(n\log n)$。