树上连通块问题

· · 个人记录

树上连通块问题

详见 2018集训队论文《解决树上连通块问题的一些技巧和工具》，这里仅作简要摘录。

1.引言

树是一种非常特殊的结构,树的任意一个连通子图（树上连通块）同样也是一棵树，若干个树上连通块的交也是一棵树。本文将重点介绍两类问题：对树上连通块计数/求最优值的 DP 问题、树上同色连通块信息维护问题。

本文主要分为两个部分，第一部分从几个例题入手,分别介绍了按 DFS 序转移及点分治、“点数-边数”、 用线段树合并进行整体 DP 、 用链分治维护动态 DP 等方法在树上连通块 DP 问题中的应用。第二部分围绕树上同色连通块问题展开,通过两个经典例题展示了该类问题的一般思路,并介绍了 Link Cut Memphis 这一支持链修改颜色并维护 DFS 序上信息的数据结构。

2.相关定义与说明

无向图 G=\{V,E\} 被称为树当且仅当任意两个点之间有且仅有一条简单路径。任意无环的连通图都是树。

树 T=\{V,E\} 的一个树上连通块 T'=\{V',E'\} 满足 V'\subseteq V ，E'\subseteq E 且 T' 连通。易知 T' 的结构也是一棵树。

本文涉及的树上连通块 DP 问题形式一般为以下两种：

本文涉及的树上同色连通块信息维护问题形式一般为：给出一棵树 T ，每个点有黑白两种颜色。定义一个树上连通块合法当且仅当其所有节点颜色相同。询问的是点 x 所在极大合法连通块的信息。

这两种问题以外可能还有若干较少见的和树上连通块有关的问题，不在本文讨论范围之内。

3.树上连通块的 DP 问题

3.1 朴素算法

对于一般的树上连通块 DP 问题，通用的朴素算法是设 dp_x 表示在 x 子树中选择一个包含点 x​ 的连通块时的方案数/最优答案。dp_x 可以由 x 的儿子的 dp 值合并得到,即遍历 x 的所有儿子,决策每个子树内是留空还是选择一个含根的连通块。

如果合并两个儿子的信息是 O(1) 的（例如求有多少本质不同的树上连通块），则总的复杂度为 O(n) ，如果合并两个儿子的复杂度为 O(size_a ∗ size_b ) （例如求多少本质不同的 k 个点的树上连通块），则任意两个点都会在它们的 LCA 处产生 1 的复杂度，总复杂度为 O(n^2)。

这种朴素算法对计数类问题和最优化问题均适用。

3.2 按 DFS 序转移与点分治

对于一类树上连通块 DP 问题，如果信息合并不够高效，但单点信息比较高效，往往可以按照 DFS 序转移，把合并子树变成添加单点。常见的有背包的模型，设体积上限为 m ，合并两个背包的复杂度为 O(m^2) ，而加入一个物品的复杂度为 O(m) 。

先假定选出来的连通块 必须包含根 ，求出整棵树的 DFS 序，一个包含根的树上连通块的结构一定形如整棵子树去掉若干个互不相交的子树。在 DFS 序中，去掉的就是连续的若干段。

设 dp_i 表示考虑了 DFS 序前 i 个节点时的信息。如果要选择第 i 个节点，则转移到 dp_{i+1} ，否则转移到 dp_j ，其中 j 是第 i 个点子树 DFS 序右端点 +1 ，表示去掉这整棵子树。

这样每次就只要往背包中添加一个物品，而不是合并两个背包。设添加单点的复杂度为 O(m) ，总复杂度为 O(nm) 。

而对于选出的连通块可以不包含根的问题，只要进行点分治，每次把重心作为根，算出强制包含重心的方案数，再把重心删除，对每个连通块递归做，总复杂度为 O(mn\log n ) 。（其实点分治上的连通块就是考虑每个分治中心是否是连通块上的点。如果不是，就会递归成若干个分治区域进行求解。）

不过感觉这个 trick 好像有点没用吧，一般 nm 同阶，且直接暴力背包的复杂度就是 O(n^2)​​ ，并没有很好的优化，不过不是基于子树大小的背包就另当别论了。

例题一

题意：给出一棵树,每个点有个颜色。给出 3 种颜色 u, v, w ，求有多少个树上连通块满足里面颜色为 u, v, w 的点的个数分别为 a, b, c 。

题解：朴素做法是自底向上 DP ，用 dp_{x,i,j,k} 表示处理以 x 为根的子树，三种颜色分别为 i,j,k 的方案数。转移合并两个子树时枚举两个子树中三种颜色各自的点数，复杂度为 O(na^2b^2c^2) 。

注意到这里合并两棵子树时一个三维卷积的过程，如果用三维 FFT 优化，复杂度能变成 O(nabc\log abc) ，但是常数和码量都较大。

考虑使用上述点分治算法，配合 DFS 序转移，复杂度为 O(nabc\log n) 。常数很小，而且可以方便地推广到最优化问题。

3.3 点数-边数

对于一棵非空的树，点数 -​ 边数恒为 1​，我们可以用这个等式来统计满足某性质的树上连通块个数，即枚举每个点/每条边，算出包含这个点/这条边的合法树上连通块个数，用点的答案减去边的答案，就能让所有合法的非空树上连通块被统计到恰好 1 次。

这个技巧常用于求若干个树上连通块的交的场合，因为若干个树上连通块的交仍然是一棵树（可能为空） 。若干个树上连通块交集非空的方案数并不容易直接计算，但如果只考虑一个点/一条边，就变成每个树上连通块都要包含这个点/这条边。树上连通块之间彼此独立，变得相对容易计算。

稍微演示一下求若干个树上连通块交集非空的方案数吧，错了轻喷。

\begin{aligned} \sum_{S_1\vee S_2\vee \cdots\ne \varnothing} 1 =&\sum_{S_1\vee S_2\vee \cdots\ne \varnothing} \text{点数-边数}\\ =&\sum_{i=1}^{n}\text{i被若干个连通块包含的方案数}-\sum_{i=1}^{n-1}\text{第i条边被若干连通块包含的方案数} \end{aligned}

对于求合法连通块数也是一样的，可以通过交换和式的思路来进行化简。

例题二

题意：给出一棵树，每个点有重量和价值，每条边有边权，考虑选出一个点的子集 S ，满足这些节点重量之和 \le M 且构成一个树上连通块，把那些价值和最大的集合 S 称为完美的集合。

如果两个点 x, y 满足 dist(x, y) ∗ v_y \le Max ，则 x 可以对 y 进行测试,问有多少种方案在所有完美的集合中选出 k 个，使得在它们的交中存在一个点 x ，能对这些集合中所有点进行测试。

答案对 5^{23} 取模。

题解： 考虑对于任意一个点集中所有点进行测试的点形成一个树上连通块（证明考虑如果点 $x$​ 不能对 $y$​ 进行测试，那么在以 $y$​ 为根的情况下， $x$​ 子树内所有点都不能与 $y$​ 进行测试。这样考虑的话，可以发现所有满足条件的点组成一个连通块）。 考虑对于 $k$ 个完美集合，它们的测试点集合若有交一定形成一个树上连通块，且这个树上连通块的贡献 $ +1$ 。用 “点数-边数” 的技巧，将这个 $+1$ 的贡献变为每个点 $+1$ 和每条边 $-1$ ，那么对于一个点 $x$ ，其贡献是选出 $k$ 个完美集合使得都包含 $x$ 的方案数。对于一条边 $(x,y)$ 的贡献是选出 $k$ 个完美集合使得都包含 $(x,y)$ 的方案数。 这样的话，对于每个大小为 $k$ 的完美集合组合，其测试点集合（一个树上连通块），每个点都贡献 $1$ 的贡献，每条边都贡献 $-1$ 的贡献，加起来恰好是 $1$ 个贡献。 现在的问题转化为计算能被点 $x$ 测试的完美集合数。这些集合肯定不能到达包含任何到 $x$ 距离不合法的点。在去掉非法点后的树中进行 DP ，相当于问有多少个树上连通块重量之和 $\le M$ 且价值和最大。这是一个经典的最优化背包问题，只要在背包统计重量之和为 $X$ 的同时记录下 $\sum v$ 的最优值和到达最优值的方案数就可以了（相同重量下，较小价值和的方案没有意义）。把 $x$ 作为根，按照 DFS 转移，复杂度为 $O(nm)$ 。 最后还涉及到一个组合数取模，和本文关系不大，不再展开。 总的复杂度为 $O(n^2m+\text{组合数取模复杂度})$ 。 **3.4 用线段树合并进行整体 DP ** 有这样一类树上连通块计数问题：每个点要维护一个大小为 $m$ 的 DP 数组，合并两个子树时，操作是把 $m$ 个 **对应位置进行合并** ，添加一个点时需要对某个位置进行修改。虽然 DP 状态有 $O(nm)$ 个，但大部分状态仅仅是重复地由子树状态合并得到的。而注意到添加一个点的操作是 $O(n)$ 级别的，如果我们能快速完成按位合并的操作，就能很好地解决这类问题。 考虑使用线段树合并，即把每个点的 $m$ 个 DP 值用一棵线段树进行维护，添加一个点时在其线段树中进行修改，合并两个子树时用线段树合并来批量完成转移。线段树中插入的总点数是 $O(n\log n)$ 级别的，而线段树合并的复杂度不高于其插入的总复杂度。 **例题三** 题意：给出一棵树，每个点有颜色，求有多少树上连通块包含不超过 $2$ 种颜色。 题解： 设 $f(x,c)$ 表示在 $x$ 的子树内选择一个包含 $x$ 的连通块，且 $2$ 种颜色分别为 $col_x$ 和 $c$ 的方案数。 讨论 $x$ 的儿子 $y$ 的颜色，不难得出转移，若 $y$ 与 $x$ 的颜色相同，则直接将所有 $f(y,\sim )+1$ 乘起来给 $f(x,\sim )$ ，否则将 $f(y,col_x)+1$ 乘给 $f(x,col_y)$ 。 第二种转移只需要 $O(n)$ 次，瓶颈在于第一种转移：每有一个同色儿子，就要花费 $O(\text{子树中颜色数})$ 的复杂度。 观察到是树上每个点的 $dp$ 值是对应位置相乘，不难想到直接线段树合并就好了。 复杂度为 $O(n\log n)$​ 。 **3.5 用链分治维护动态 DP** 动态 DP 是指支持对 DP 的输入进行修改，并在每次修改后快速求出 DP 值，一般用于计数类问题。在 2017 年的集训队论文中，陈俊锟提出了一种具有扩展性的解决树上动态 DP 问题的算法——链分治。这里将链分治算法应用到树上连通块动态 DP 问题。 具体地，我们需要对节点的信息进行修改，并在每次修改后求树上连通块计数类问题的答案。 链分治的思想是将树进行轻重链剖剖分，按照重链从底向上依次计算 DP 值。对于一条重链，其延展出去的子重链的 DP 值信息已经计算完毕，可以把它们的信息附着在这条重链上，然后就变成了一个序列上的动态 DP 问题。而序列上往往可以使用数据结构来支持修改。 修改一个点的信息时，根据这个分治结构，只会有 $O(\log n)$ 条重链的信息需要修改。从底向上依次在每条重链的数据结构中修改并维护 DP 值即可。 一般地，设 $G(x)$ 表示在 $x$ 子树内选择一个含根的连通块时的答案，对于一条重链，设上面的节点按深度从小到大排序为 $x_{1\sim k} $ 对于每个节点 $x_i$ ，都已经求出了它所有轻儿子的贡献 $G()$ 值，把这些信息与 $x_i$ 本身的信息进行合并，就能得到这条重链上选择 $x_i$ 这个点时的贡献，设这个值为 $F(x_i)$ 。 如果选出的树上连通块和这条重链有交，交集必然是个区间，贡献是这个区间的 $F(x)$ 之积。亦即求这条重链上某个区间的 $F(x)$ 之积。只要使用线段树/平衡树即可。 而这条重链对于其父重链的贡献，就是在这条重链上选择一个前缀的方案数，只要用线段树/平衡树/维护出的前缀信息去更新其父节点的 $G()$ 值就可以了。 至此这个算法的框架已渐渐清晰，对树进行轻重链剖分，按照重链自底向上的顺序计算 DP 值。修改一个点的信息时，对于其祖先中的每条重链，在线段树/平衡树中重新选出一个前缀的方案数，并用这个方案数去更新这条重链的父亲的信息。 如果需要维护的信息可减，在修改子重链的信息后，直接减去旧的信息，加上新来的信息就可以了。否则还需要对于每个点开一个 $O(\text{轻子树个数})$ 的线段树或平衡树来快速维护轻儿子们的信息，但是复杂度时不变的。 **例题四** 题意： 给出一棵树，每个点有点权。有 $2$ 种操作，形如 $1$、Change x y ，将编号为 $x$ 的节点的权值改成 $y$ 。 $2$、Query k ，询问有多少非空连通块，满足其点权的异或值恰好为 $k$ 。 输出对 $10007$ 取模。 $n, Q \le 30000, 0 \le A_i , y, k < 128$ 。 题解： 并考虑如果是要你求出对于每次询问的 $k$​ ，那么不可能像之前那样逐位判断就能成功的。结合值域较小的性质，考虑这个问题的经典解决方案就是 FWT 了，对于每个点第 $A_i$ 位为 $1$​ ，那么就是把异或值全都转成 FWT 的点值，运算过程中全部用点值计算，最后再 FWT 回去。设 $m$ 为权值的最大值，合并信息的复杂度就是 $O(m)$ 。 由于我们求的是连通块，所以我们用 $G(x,\sim )$ 表示再 $x$ 子树中选择一个含根的连通块的点值。对于重链上的一个点，算出其轻儿子的 $G(y,\sim )+1$ 之积，然后数据结构维护一个区间的方案数，再用选择一个前缀的方案数来更新重链父亲的 $G(fa,\sim )$ 。 由于维护的是积，所以在去掉一个轻儿子的旧的贡献时，可能会面临除 $0$ 的问题，一个解决方法时维护模 $10007$ 非 $0$ 的值的积和 $10007$ 的幂次。 因为每个点维护的轻儿子的信息是具有可减性的（即一个值的变化带来的结构可以快速知道）。每次修改一个点只会改变其到根的链上 $O(\text{轻儿子})$ 个权值，每更新一次权值需要查询一条重链上的权值乘积，用树链剖分的复杂度是 $O(qm\log^2 n)$ 。 如果用 LCT 维护链分治结构，在 access 的时候动态地维护轻重链关系并维护答案，复杂度可以做到 $O(qm\log n)$ ，而且可以更方便地询问一些子结构的 DP 信息，如询问某个点子树中的答案，或和某条路径 $u,v$ 有交的答案等，还能支持 Link/Cut 操作。不过写起来看上去很麻烦。 **3.6 总结** 树上连通块 DP 问题一般分为计数类问题和最优化问题。 如果合并两个 DP 状态的复杂度较高，而添加一个点的复杂度较低，例如大部分的背包问题，往往可以用按 DFS 序转移代替朴素的自底向上转移。如果所求的树上连通块不一定强制包含根的连通块信息，可以多花费 $O(\log n)$ 的复杂度进行点分治，每次把重心定为根，求出强制包含根的连通块信息，在递归每个连通块。 “点数-边数”的技巧常用于选多个树上连通块交非空的计数类问题中。通过在做 $O(n)$ 次强制包含某个点/某条边的 DP ，能让不同的树上连通块彼此独立。特别的，如果题目要求的是树上连通块两两有交，也等价于其全部交起来非空。 对于大部分时间花在合并两个子树 **对应位置信息** 并重新对树上连通块计数的问题，可以用树链剖分或 LCT 来维护动态 DP ，本质上是利用其信息满足结合律的条件。对每条重链求其一个区间的答案和，再用选一个前缀的答案和更新其父重链的答案。 ## 4.树上同色连通块维护问题 **4.1 一般思路** 考虑一棵黑白两色的树，对于每个极大的同色连通块，其最浅点，即整个连通块 LCA 是唯一的，且可以通过树链剖分或者 LCT 快速找到，即求某个点到其最近异色祖先路径上异色祖先的儿子节点。我们不妨把信息维护在这个最浅点处。 最浅点颜色改变时，连通块的形状会有较大的变化，原本与其同色的儿子变为异色，而原本异色的儿子变成同色。如果直接维护 “点 $x$ 子树内与 $x$ 同色的连通块的信息” ，要花费 $O(\text{儿子个数})$ 的时间。 解决的办法是在每一个节点上记录两种颜色的信息，即如果一个点是黑色/白色时，以它为最浅点的该种颜色连通块的信息，这样修改它的颜色时，它本身的信息不需要修改，只要在父节点处添加和删除这个点的信息就可以了。 如果颜色数不是两种，而是一个较小的常数 $k$ ，那么可以维护 $k$ 个数据结构，第 $i$ 种结构把第 $i$ 种颜色当作黑色，其余颜色当作白色处理。这样可以以复杂度乘 $k$ 的代价支持多种颜色的维护。 **例题五** 题意 给出一棵树，每个点有黑白两种颜色，要求支持两种操作： - $1.$ 询问点u所在同色连通块的大小。 - $2.$ 翻转点u的颜色,即黑色变白色,白色变黑色。 $n,q\le 10^5

题解：

考虑在每个点上维护两个值 B(x) 和 W(x) ，分别表示如果点 x 是黑色/白色时，以它为最浅点的该种颜色同色块的大小。

对于询问操作，设询问的是点 u ，且它是白色，只要找到 u 所在的白色连通块的最浅点 v ，输出 W(v) 就好了。

考虑翻转点 u 的颜色，假设是从白色改成黑色，只要找到 u 往上第一个黑色节点 v ，把 (u,v] 的 W() 值都减去 W(u) ，再找 u 往上第一个白色节点 v ，把 (u,v] 的 B() 值加上 B(u) 就完成维护了。

“ u 往上第一个白色/黑色节点 ” 可以用数据结构维护链上区间内两种颜色的点数来进行查找，如果用树链剖分 + 线段树，复杂度是 O(n\log^2 n) ，如果用 LCT ，复杂度为 O(n\log n) 。

例题六

题意

给出一棵树，每个点有黑白两种颜色，还有个点权，要求支持三种操作：

题解： 与上一题不同的是，这题要维护最大值，并不能像上一题一样直接把贡献减掉。 观察上一题中维护的信息的本质，如果一个点是白点，其信息就会被加到父节点的 $W()$ 中。若是黑点，则被加到父节点的 $B()$ 中。 相当于有一棵黑树和一棵白树，黑点在黑树中与其父亲相连，白点在白树中与其父亲相连。每棵树中每个连通块除了最浅点，都为该种颜色。询问一个点所在同色连通块信息时，同样是找到其最浅同色祖先，询问其整个子树信息即可。 考虑 LCT ，在每个点上维护一个 multiset 记录其所有轻儿子子树中的最大点权，在 splay 上同时维护重链的最大点权。 在 access 切换轻重边时，在 multiset 里更新信息，插入原先重儿子的值，并删去新的重儿子的值。修改点权只要先 access 就能方便维护。 修改一个点的颜色，比如把 $u$ 从白色改成黑色，若 $u$ 非根节点，就在白树上断开 $u$ 与黑树的边，在黑树中连上 $u$ 和父亲的边就可以了。 每次切换轻重边时有个 multiset 的 $O(\text{轻儿子个数})$ 的复杂度，根据 Top-Tree 的复杂度证明，这个做法复杂度是 $O(n\log n)$ 的。 其实我们本质上是开了一棵黑树和一棵白树（可能不连通）。对于一个白点，我们在白树上连一条父亲和它的边，对于一个黑点，我们在黑树上连一条父亲到它的边，那么我们就容易维护出同色连通块。如果修改，直接在两棵树上 link/cut 就可以了。对于上一问，其实就是求这个连通块的大小（根节点特判），而这里就是问子树中最值。 而这个也是一样的，每个点记录一个 $mx$ 表示这个点子树内（更准确的说是实子树和虚子树）中的最大值， $mx2$ 表示这个点虚子结点的 $mx$ 的最大值。因为这里最大值有删除，所以要开个 multiset 来存下每个虚子结点的 $mx$ 。pushup,rotate,splay 什么的不改变虚实关系，只有 access 进行的时候稍微搞一下就行了。 **4.2 维护 DFS 序上的任意信息** 对于更复杂的信息，只要满足结合律且能快速合并，换言之就是能用数据结构在 DFS 序上维护，都可以套用上面的做法。 观察上面提到的黑树/白树的形态，可以发现其和原树是完全一致的，而且整个过程中都不需要用到换根操作，也就是说可以直接按照原树的 DFS 序进行维护。 考虑用一种支持提取区间的平衡树，如 Splay 或 Treap 来处理，再 LCT 里 Link/Cut 时，到平衡树中提取子树拼入父节点 DFS 序中，或将子树与父节点分离开来。 不难发现上面的题其实就是在原树的模板上砍子树和加子树，所以其 DFS 序还如以前，所以可以省掉 multiset ，维护出每个连通块的 DFS 序，提取子树和插入子树，这样的话直接额外拿个平衡树维护就可以了。 一次平衡树操作复杂度为 $O(\log n)$ ，所以总复杂度为 $O(n\log n)$ 。 **4.3 链修改颜色** 对于链修改颜色,这里介绍一种由陶渊政提出的基于 LCT 的数据结构。 把一条链上所有点的颜色都改成黑色/白色,如果将链颜色覆盖看成 LCT 操作,可以将问题转化为 $O(n log n)$ 次同色链反色。 **4.3.1 新的黑/白树定义** 效仿前面的做法，仍然时维护黑树和白树，不过要修改两者的定义，以一条白点 $u$ 为例。 【鸽子，咕掉了， LCM 这东西看起来就阴间，学了也写不出来，鸽掉了。。。】 这里只想搞一个求树上连通块直径的方法罢了。 ![](https://cdn.luogu.com.cn/upload/image_hosting/oiz4pu8d.png) ![](https://cdn.luogu.com.cn/upload/image_hosting/805jsma6.png) 不过稍微想了一下，记得以前有一个做法就是树上两个点集（可以不连通）合并，新点集的直径可以由原先那两个点集中构成直径的那 $4$ 个点组合得到。只要 Treap 维护 DFS 序的同时维护一下直径就好了。 不过万弘说如果可离线的话，直接线段树分治就可以了，的确。