树上算法

Published: by Creative Commons Licence

  • Tags:

轻重链技术

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

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

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

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

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

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

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

一道CF题目

dsu on tree

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

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

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

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

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

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

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

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

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

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

边分治

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

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

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

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

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

边分树

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

dist(u,v)=dist1(u,v)+dist2(u,v)

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

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

点分治和动态点分治

点分治的基本原理是找到树的重心。一个顶点称为重心,当且仅当删除它之后,得到的所有连通块大小都不超过树大小的一半。可以证明重心始终是存在的,并且一颗树的重心数目最多只有两个。

点分治的流程如下:

  • 找出树的重心C
  • 统计经过C的所有路径信息。
  • 删除C
  • 对得到的新的连通分块递归调用这个流程。

点分治的用处是统计一些满足特殊性质的路径,比如长度不超过k的路径数目。可以发现点分治的深度最多为log2n,且每个顶点在一层最多贡献一次,因此总的顶点贡献次数为O(nlog2n)

一般点分治是离线操作,但是如果我们根据这个流程构建点分树就可以实现在线操作,其原理类似于离线二分,将每次流程的数据保留下来,根据流程的调用关系,可以构建一颗深度不超过log2n的树。

之后对于查询操作,我们可以从顶点出发,不断向上跳。但是这里依旧有一些难点,比如说在处理重心C的时候以及其某个孩子u,如何获取不包含以u为根的子树的信息,这个一般只能通过差分的技术来完成,或者通过持久化技术来做。

如果在上面的过程中,我们使用的是差分技术,那么我们可以基于点分树实现动态点分治,即允许单点修改操作。具体的原理是为每个顶点i维护两个信息,Ai表示以i个重心的流程的统计信息,Bi表示该流程代表的连通块,对父流程的贡献。之后对于单点操作,我们修改AB最多各log2n次。

题目1:给定n个顶点,每个顶点都有各自的点权。之后q个请求,请求分为两类:

  • 修改某个点的点权
  • 给定uk,统计所有距离u不超过k的顶点的点权和。

提供一道题目

动态点分治的裸题。

树上最远点对

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

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

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

树上中点(边)

如果一颗树的直径为D

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

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

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

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

最小子树统计

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

要求:SVf(S)

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

SVf(S)=SV(eg(S)1+1)=SVeg(S)1+2|V|=eESV[eg(S)]+2|V|

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

SV[eg(S)]=2|V|2L(e)2R(e)+20

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

SVf(S)=eESV[eg(S)]+2|V|=eE(2|V|2L(e)2R(e)+20)+2|V|

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

长链剖分

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

长链剖分类似于dsu on tree。

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

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

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

证明:

如果xy处于同一长链,很显然成立。

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

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

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

之后对于诸如询问询问xk级祖先,我们用倍增先找到xhb(k)级祖先y,这里hb(k)表示的是k的最高二进制位,之后对于k=khb(k),可以推出k<hb(k),而我们由性质2得到y所在的长链的长度至少为O(hb(k)),因此我们可以直接利用y所在长链顶部顶点的AB数组直接查表得到。

查询树上最长k边路径

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

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

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

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

树上路径查询

一般在线树上路径查询请求可以用LCT通吃,这里使用长链剖分可以做到O(1)回答静态请求。

比如我们要求查询路径上最大权的边。对于u,v路径,记lca为t我们可以将u,v之间路径切分成两部分,utvt。这里仅讨论ut。记二者之间距离为k,首先找到uhb(k)级祖先a,以及二者之间的最大权边,这里用倍增预处理就可以搞定了,时间复杂度为O(n)。接下来考虑at的路径,我们可以为a所在直链的顶部顶点a预处理一条长度为直链长度的数组A,其中Ai表示ai级祖先到a路径上的最大权边。当然如果taa之间,则在同一条直链上,此时我们可以根据直链分配连续编号,之后根据编号建立sparse table,这样就能保证O(1)级别的查询了。

双树问题

双树问题是指提供两颗树,在两棵树上做各种操作,且要满足一些约束条件。

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

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

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

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

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

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

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

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

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

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

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

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

Codeforces上有一道原题

题目3:给定两颗都包含n个顶点的树,判断存在多少结点对(a,b),其中a<b,且满足在一棵树中ab的祖先,而在另外一颗树种ba的祖先。

换言之问题实际上问,对于第一颗树来说,它有多少祖先是它在第二颗树上的后代。

我们可以按照第二颗树的dfs序重新为结点编号,这样每个在第二颗树上,子树形成连续区间。

现在我们可以dfs第一颗树,并维护所有祖先出现的位置,而要统计某个结点的在第二颗树的后代的出现次数,只需要统计范围和即可。我们可以用一个二叉索引树来维护,时间复杂度为O(nlog2n)

一类树上分割问题

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

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

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

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

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

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

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

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

上面的优化后的算法的时间复杂度为O(nnlog2n),但是实际上我们可以选择暴力计算到nlog2n,这样真实的时间复杂度就会降低到nnlog2n

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

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

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

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

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

树上路径统计问题

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

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

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

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

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

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

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

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

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

这三种方式各有优劣:

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

问题3:给定一株拥有n个顶点的树,每个顶点都有点权。现在定义路径(u,v)上的顶点的权重分别为x1,x2,,xk,定义f(u,v)=ki=1(ki+1)xi,要求计算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)表示路径总长。

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

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

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

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

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

提供CF原题

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

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

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

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

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

|AB|=|A|+|B||S|

对第二个条件也可以转换为2bax2y的形式,我们用同样的RMQ技术维护即可。

总的时间复杂度为O(n(logn)2)

提供一道题目

题目5:给定一颗拥有n个顶点的树,每个顶点都有一个编号。现在要求在线回答m个请求,每个请求指定两个顶点u,v以及一个整数k,要求找到u,v之间唯一路径上第k小的顶点编号。

提供一道题目

我们为每个顶点维护一个权值线段树,记录从根到这个顶点的路径上每个编号的出现次数。可以发现如果我们这里借助持久化技术,可以保证时空复杂度为O(nlog2n)

之后对于每个请求,记l=lca(u,v)pll在树上的父亲。那么二者路径上的统计关系可以通过u+vlpl(这里表示的线段树的加减法)来获得。我们不需要完全算出整颗树,只需在上面二分即可,这样只会处理最多O(log2n)个顶点而已。

总的时间复杂度为O((n+m)log2n)

题目6:给定一颗拥有n个顶点的树,每个顶点都有一个编号。现在要求在线回答m个请求,每个请求指定两个顶点u,v以及一个整数l,r,要求找到u,v之间唯一路径上在[l,r]区间中的最小的出现奇数次的编号,如果不存在,则输出1

提供一道题目

我们为每个编号进行哈希,哈希到某个64位整数。之后我们为每个顶点维护一个线段树,线段树中记录从根到这个顶点的所有编号的哈希信息,哈希信息通过异或合并在一起。这里通过持久化可以做到O(nlog2n)的空间和时间复杂度。

之后对于每个查询操作,记l=lca(u,v)pll在树上的父亲。那么二者路径上的统计关系可以通过uvlpl(这里表示的线段树的异或运算)来获得。我们不需要完全算出整颗树,只需在上面二分即可,这样只会处理最多O(log2n)个顶点而已。

下面计算一下冲突的概率。可以发现一个区间异或和为0的时候,其中某个编号出现奇数次的概率为1264。而一个区间异或和非0的时候,则必定存在一个编号出现奇数次。因此我们这边失败当且仅当在执行二分操作的时候,某个区间异或和为0,但是实际上某个编号出现了奇数次,即每次操作成功的概率为11264。而总共有O(mlog2n)次的二分操作,记Ai为第i次成功的实验集合,成功概率为Pr(iAi)=1Pr(i¯Ai)1iPr(¯Ai)=1mlog2n264。非常大的。

LCA算法及应用

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

LCA的性质:

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

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

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

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

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

子树划分问题

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

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

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

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

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

一类树划分问题

有一类问题,是给出一颗树T,之后对每条边e计算删除它后得到的两棵树Ae,Be,要求我们求eTf(Ae,Be)

这类问题假如直接暴力枚举每条边,之后对得到的两棵树进行DFS,这样的时间复杂度会达到O(n2)。但是可以发现每条边一定连接父子两个顶点,因此如果我们维护两棵树的实时信息,那么当我们沿着边从父亲移动到孩子,两棵树的变化量非常小。这也给我们提供了一种维护增量变换信息的思路来优化时间复杂度。

举个例子:给定一颗树,每个顶点的编号从1n。要求我们计算对每条边删除后得到的两颗子树最大值之积的和。换言之,计算eTmax

用我们提到的方法,我们可以为每个顶点u,计算出以u为根的子树中最大编号,记为Sub(u)

之后考虑如何计算结果。我们对树进行dfs,假设我们抵达了某个顶点u。我们实时维护在删除了u子树后其余顶点组成的树F中的最大值M。之后我们考虑枚举子边(u,v),很显然此时(u,v)边删除后,记u所在的子树为A_e,而v所在的子树为B_e。很显然B_e的信息是已知的(即Sub(v)),那么现在我们需要计算的就是A_e。可以发现A_e可以是由三部分组成的,u本身,Fu的其余孩子。其中u的其余孩子信息比较难统计(比如u的孩子非常多)。这里有一个简单的技巧,就是维护一个前缀和和后缀和,那么u的其余孩子实际上就是由前缀和和后缀和合并后可以快速计算出来。

在上面问题中时间和空间复杂度为O(n)

题目1:给定一棵包含n个顶点的树,其中一些顶点是白色的,一些顶点是黑色的。要求从树中删除一条边后再加入一条边,要求形成一颗新的树,要求让互相连通的白色顶点对尽可能多。两个白色顶点对是连通的,当且仅当两者之间的唯一路径上的顶点都是白色顶点。其中1\leq n\leq 10^6。要求输出最多的连通的白色顶点对数((a,b)和(b,a)认为是相同的顶点对)

这个问题就用到了上面提到的技术。如果树上所有白色顶点对都已经连通了或者根本不存在白色顶点对,那么问题就非常简单。这里不细讲这种情况。

下面我们考虑至少存在两个白色顶点是不连通的情况。这时候我们可以断定被删除的边两端至少有一个黑色顶点,而加入的新边两端都是白色顶点对。有了这个断言,我们就可以非常简单的解决这个问题了。

首先我们为每颗子树预先计算出其中最大的白色顶点连通块大小。那么我们从上至下dfs的时候,实际上可以通过枚举四种情况(父边连接的子树、前缀、后缀、自己)来快速计算出边的上下子树信息。并且我们不必考虑那些两端都是白色顶点的边以及删除它们带来的影响。

时间复杂度为O(n)

树上匹配问题

题目1:给定n个顶点的树(n是偶数),我们要将所有顶点两两配对,其中顶点u和顶点v配对的权值为dist(u,v),即两个顶点在树上唯一路径中的边数。现在要求将所有顶点两两配对,且要求计算最大的可能权重和最小的可能权重。

我们知道树上距离的计算公式为dist(u,v)=depth(u)+depth(v)-2\cdot depth(lca(u,v))。记所有分组的集合为P,则总权重为:

\begin{aligned} W(P)&=\sum_{(u,v)\in P}dist(u,v) &=\sum_{(u,v)\in P}depth(u)+depth(v)-2\cdot detph(lca(u,v)) &=\sum_{v\in V}depth(v)-2\cdot \sum_{(u,v)\in P}depth(lca(u,v)) \end{aligned}

因此我们要让权重最大,需要让\sum_{(u,v)\in P}depth(lca(u,v))最小。对应的要让权重最小,需要让\sum_{(u,v)\in P}depth(lca(u,v))最大。

在求最大的情况,我们可以对树进行DFS,并尽可能将LCA设置为当前遍历的顶点。而在求最小的情况,我们同样对树进行DFS,但是尽可能在遍历子树的时候就将子树中的顶点配对。

时间复杂度为O(n)

实际上这里要让权重最大,我们可以直接找到树的重心即可,将重心作为根,这时候所有配对顶点的lca都是根。

题目2:给定n个顶点的树(n是偶数),我们要将所有顶点两两配对,其中顶点u和顶点v配对的权值为dist(u,v),即两个顶点在树上唯一路径中的边数。现在要求将所有顶点两两配对,且要求所有配对的总权值正好为k。要求输出配对方案。其中2\leq n\leq 10^5

提供一道题目

我们可以先找到树的重心,之后我们将重心作为树根。我们不考虑配对的权重,而是通过考虑每条边的贡献。考虑一条边e,其将树分成xn-x两部分。可以发现配对的顶点落在不同的部分的配对数的奇偶性与x相同,记f(e)=x\pmod 2,记g(e)=\min(x, n-x)

考虑题目1中我们让总权最大和最小的算法,我们可以证明最小权值为m=\sum_{e} f(e),而最大权值为M=\sum_{e}g(e)。同时mM拥有相同的奇偶性。且kmM拥有相同的奇偶性是有解的必要条件。

下面我们考虑在m\leq k\leq MkM具有相同奇偶性的前提下,进行求解。

可以发现如果我们选择根下的最大一颗子树T,并从中删除任意两个顶点,那么根依旧是树的重心(一般情况下,这是不满足的,但是需要注意n是偶数)。我们具体删除那两个顶点呢,我们选择深度最大的叶子,之后从从它的父亲列表删除两个孩子(如果孩子只有一个,就将父亲一同删除),可以发现T依旧是一棵树。但是可能这样会导致当前的总权值低于k,这时候我们可以暴力找到一个深度恰好的顶点,删除它和它的某个孩子即可。

树上监视问题

题目1:给定n个顶点的树,现在要求在一些顶点上放置k个监视器。其为每个顶点u维护一个向量v^{(u)}=(v^{(u)}_1,v^{(u)}_2,\ldots,v^{(u)}_k)。其中v^{(u)}_i表示的是监视器i到顶点u的最短距离。我们希望让所有顶点对应的向量都不同,问k的最小值是多少,并且求出一组放置方案。

首先任意顶点u,我们将u作为树根。考虑u的所有子树。可以发现如果同时有两个子树中都不放监视器,那么这两个子树的根的向量一定相同。因此我们可以发现,对于任意树,其子树中最多有一个子树没有放监视器。

我们可以在树上进行一次dfs。之后如果我们发现有多于一颗子树没有放监视器,我们就取任意一个没有放置监视器的子树中的叶子顶点,放入一个监视器。

如果有一个子树中没有放任何监视器,且u不是根顶点,这时候我们需要要求在u子树外其余顶点中至少放一个顶点。同时我们发现一些子树要求子树外顶点至少放一个监视器。我们将这个属性继承到当前顶点u中。我们永远不在当前顶点放监视器。

最后在处理根结点的时候特殊处理,因为此时根顶点依旧要求在外部至少放一个顶点,我们从中选择一个空叶子顶点放入监视器。

这个做法是O(n)的。

题目2:给定n个顶点的树,现在要求在一些顶点上放置监视器。每个监视器能监视距离到它所在顶点不超过D的所有结点。问至少需要放置多少个监视器,才能监视到树上所有顶点,其中1\leq D\leq n\leq 10^5

讲一个简单的贪心思路,就是每次枚举最深的未被监视的顶点v,找到它的D级祖先u,在u上放一个监视器。

先说明这个思路为什么是正确的。考虑到要监视v,那么必定在u的子树中需要放置一个监视器。但是如果这个监视器放置在u上,则不仅可以监视到整颗子树中的所有未被监视的顶点(因为v是最深的,其它未被监视的顶点的深度都小于它,自然也会被监视到),同时还能监视到最大范围的子树外的顶点。

但是仅靠这个思路,实现会有问题。因为这会导致最多O(kn)的时间复杂度,k为实际放置的监视器数量。

这里我们可以发现一个非常简单的事实,就是k\leq \left \lceil \frac{n}{D}\right\rceil。为啥呢,非常简单,我们考虑上面的过程,每次选择一个顶点放置监视器,并删除这个顶点为根的整个子树。可以发现每次都至少会删除k个顶点(除了最后一次)。了解了这个性质,就可以为每个顶点维护一个距离最近监视器的距离。很显然每次放置监视器后更新所有周边顶点的时候,如果发现这个顶点距离之前最近的一个顶点的距离不大于到新监视器的距离,就可以跳过这个顶点。因此每个顶点最多被更新D次,总的时间复杂度为O(\min(D,\left \lceil \frac{n}{D}\right\rceil)n)\leq O(n\sqrt{n})

但是实际上如果我们继续观察,可以发现一个顶点v上放监视器,当且仅当其子树中存在一个为被监控的顶点,距离uD,或者u为根。这提供了一个DP的思路。具体做法就是记A(u)表示在以u为根的子树中的监视器数,B(u)表示以u为根的子树中的距离u最远的未被监视的顶点的距离,C(u)表示以u为根的子树中的距离u最近的放置监视器的顶点的距离。这样一次dfs就可以得到所有的状态,时间复杂度为O(n)

度数转树问题

题目1:给定n个顶点,其中2\leq n\leq 10^5。以及每个顶点的度数,d_1,\ldots,d_n,满足1\leq d_i,且\sum_{i=1}^nd_i=2(n-1)。要求找到任意一颗树。

我们考虑两个顶点ij合并的意义,此时两个顶点合并后的连通块的度数为d_i+d_j-2。并且如果不是最后一次合并,那么度数d_i+d_j-2就不能为0,换言之,我们不能把两个度数都为1的顶点合并。

所以下面就是我们的算法:

  • 我们每次挑选两个度数最大的联通块合并。

下面我们通过维护不变式\sum_{i=1}^kd_i=2(k-1)1\leq d_i,其中k是剩余的连通块数,来证明上面的算法是正确的,

n>2的时候,我们可以断言至少有一个顶点的度数超过1,否则\sum_{i=1}^kd_i\leq k<2(k-1),与前提相悖。这时候合并后的连同块的度数至少为1,所以我们的不变式还是成立的。而当n=2的时候算法是正确的,此时我们成功得到了一颗树。

可以同时发现1\leq d_i,且\sum_{i=1}^nd_i=2(n-1)是树存在的充分必要条件。

题目2:给定n个顶点,其中2\leq n\leq 10^5。以及每个顶点的度数,d_1,\ldots,d_n,满足1\leq d_i,且\sum_{i=1}^nd_i=2(n-1)。要求找到一颗匹配最大的树。

根据题目1,我们发现1\leq d_i,且\sum_{i=1}^nd_i=2(n-1)是树存在的充分必要条件。

我们在建树之前先贪心将未匹配的两个顶点两两合并。而度数为1的顶点不能与度数为1的顶点合并,因此我们可以先将度数为1的顶点和度数大于1的顶点合并,之后如果有多余的度数大于1的未匹配顶点,就将它们两两合并即可。

可以发现上述的算法不会影响树是否存在。

m为度数为1的顶点的数目。可以发现最大匹配为\min(n-m,\frac{n}{2})。但是n=2的时候我们需要特殊判断,此时结果为1

提供一道题目

题目3:给定n个顶点,其中2\leq n\leq 10^5。以及每个顶点的度数,d_1,\ldots,d_n,满足1\leq d_i,且\sum_{i=1}^nd_i=2(n-1)。要求找一颗直径恰好为D的树,保证树存在。

提供一道题目

如果D=1,则暴力处理。

否则我们可以考虑生成一颗直径最小的树,将顶点按照度数从大到小排序,之后以度数最大的顶点为根,以BFS的形式生成整颗树。

而现在给定了直径,因此我们应该在上面的流程中的某一步中断,并将剩余度数大于1的顶点追加到距离根最远顶点的尾部,剩余的度数为1的顶点再一一补上。

时间复杂度为O(n\log_2n)

树上距离和

题目1:给定n个顶点和n-1条带权边,形成一颗树。现在记dist(u,v)表示顶点u和顶点v的距离。要求对于i=1,\ldots,n,计算\sum_{j=1}^ndist(i,j)

跑一次dfs,令每个顶点维护子树大小,以及子树距离和。之后再跑一次dfs,传入子树外顶点到当前顶点的距离和和顶点数。这样加起来就可以了。

时间复杂度为O(n)

题目2:给定n个顶点和n-1条带权边,形成一颗树。现在记dist(u,v)表示顶点u和顶点v的距离。要求对于i=1,\ldots,n,计算\sum_{j=1}^ndist(i,j)^2

首先我们可以考虑距离公式:

dist(a,b)=depth(a)+depth(b)-2\times depth(c)

其中depth(x)表示x的深度,而c=lca(a,b)。之后我们把公式套入得到:

\begin{aligned} dist(a,b)^2&=depth(a)^2+depth(b)^2+4\times depth(c)^2\\ &+2depth(a)depth(b)-4depth(a)depth(c)\\ &-4depth(b)depth(c) \end{aligned}

考虑固定a,要计算\sum_b dist(a,b),需要知道

\left\{ \begin{array}{l} \sum_b depth(b)^2\\ \sum_b depth(lca(a,b))^2\\ \sum_b depth(b)\\ \sum_b depth(b)depth(lca(a,b)) \end{array} \right.

现在考虑我们维护了一个数组A,其中A_i表示depth(lca(i,a))。考虑我们处理完顶点a后,切换到顶点a的某个子结点v,那么A数组中仅v的子树对应的元素需要改变,统统变成depth(v)。如果我们在A中用顶点的dfs序号来作为下标,那么子树就对应一个连续的区间。这样我们就得到了O(\log_2n)切换顶点后维护A的技术。考虑depth(b)^2depth(b)等其它状态也可以类似维护。总的时间复杂度为O(n\log_2n)

但是实际上如果用题目1的方式,从父结点向子结点传入上部的信息,可以O(n)实现这个流程,但是对应的逻辑也更加复杂。

树上路径中最大权边

给定一颗n个顶点的树,要求回答q个请求,第i个请求要求查询u,v路径上最大权重的边的权重。其中1\leq n\leq 10^61\leq q\leq 5\times 10^6

来源

我们可以跑一次kruskal算法,在加入边(x,y)的时候,我们在创建一个新的顶点,将顶点的左孩子设置为x,右孩子设置为y,这样查询树上最大权的边等价于查询LCA。时间复杂度为O(n\alpha(n)+m),这里我们可以基数排序来对边排序。

括号序列/dfs序

我们可以把一颗大小为n的树唯一的转换为一个长度为2n的括号序列,具体做法是对树进行遍历,进入某个顶点的时候,在括号序列尾部插入一个左括号,离开某个顶点的时候插入一个右括号。每个顶点对应一对匹配的左右括号。

同理一颗合法的括号序列(同时最左边的左括号和最右边的右括号匹配)也唯一对应一颗树。

括号序列的好处是我们可以把树作为字符串进行操作,而对于字符串我们可以将其丢到平衡树上进行加速,这样就可以实现O(\log_2n)级别的字符串各种骚操作,如果愿意舍弃一些内存,还能支持持久化。

来看看括号序列有哪些好,括号序列的表示方式,可以允许我们O(\log_2n)时间复杂度下完成下面所有操作:

  • 子树的删除:我们可以删除一颗子树,对应的就是删除一段括号序列。
  • 子树的插入:类似于删除,只不过变成插入一段括号序列。
  • 查找k级祖先:考虑顶点v,要找它的深度为h的祖先,可以去二分找v右括号后第一个深度小于等于h的顶点,由于是在平衡树上二分,所以时间复杂度为O(\log_2n)
  • 查询lca:对于给定顶点u,v,如果二者为根的子树对应的括号子串有相交,那么较大的为lca。否则二者不相交,记u的括号对出现在前,那么在u的右括号到v的左括号之间的深度最小的顶点的父亲,就是它们的lca。找父亲,可以于用查找k级祖先提到的方法。
  • 子树修改查询:对应的就是一段区间的修改查询。
  • 查询两点距离:维护每个顶点的深度,查找lca后用距离公式计算。
  • 查找dfs序最大/小的深度为k的顶点:这个实际上对应的就是查找最靠右深度大于等于k/最靠左深度大于等于k的顶点。直接在平衡树上进行二分即可。

但是这样维护括号序列是不能支持换根的,要换根需要用到euler tour tree。

提供一些问题: