树上连通块问题学习笔记

· · 个人记录

树上连通块问题学习笔记

1.前置知识

树剖，点分治，线段树合并，lct ，top tree 等一切毒瘤数据结构。

2.主要内容

总结一些常见的维护树上连通块的数据结构和技巧。

3.正题

3.1 DFS序转移+点分治

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

3.1.1 选出的连通块必须包含根

设 dp_i 表示考虑了 DFS 序前 i 个节点时的信息。如果要选择第 i 个节点，则转移到 dp_{i+1}， 否则转移到 dp_j，其中 j 是第 i 个点子树DFS序的右端点+1 ，表示去掉这整个子树。这样每次就只要往背包中添加一个物品，而不是合并两个背包，设添加单点的复杂度为O(m)，总的复杂度就是O(nm)。

3.1.2 选出的连通块不必包含根

考虑进行点分治，每次把重心作为根，算出强制包含重心的方案数，再把重心删除，对每个连通块递归做。总的复杂度为O(nm\log n )。

例题1

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

做法

考虑朴素做法，设 dp_{x,i,j,k} 表示处理了以 x 为根的子树，三种颜色个数分别为 i ,j, k 的方案数,但是这样合并子树的效率是 O(a^2b^2c^2)。

考虑用DFS序转移+点分治的做法，每次加入单点的效率为 O(abc)，因为没有限制必须选根，所以要加上一个点分治的复杂度总效率为O(nabc\log n)。

3.2 “点数-边数”

简单的来说，就是对于每一个点，算出必须包含这个点的合法的连通块的数量，然后把所有点的答案加起来，然后你发现某些相同的联通块被会加多次，于是你对于每一条边，算出必须包含这条边的合法的连通块的数量，把点的答案减去边的答案，考虑到一个树的联通块上，点-边=1，所以每一个合法的连通块都会被恰好算入一次。

这种做法一般用于求于求若干个树上连通块的交的场合，因为若干个树上连通块的交仍然是一棵树（可能为空）。

例题2

3.3 线段树合并进行整体DP

感觉很板。

例题三

给出一棵树，每个点有颜色，求有多少树上连通块包含不超过2种颜色。

做法

设f(x, c)表示在 x 的子树内选择一个包含 x 的连通块，且2种颜色分别为 col_x 和 c 时的方案数。

考虑线段树合并，然后分类讨论一下儿子和自己颜色的异同进行合并就好了。

3.4 用链分治维护动态DP

一般用于修改某个点对于整棵树的贡献，若设的状态只和子树有关，那么每次修改单点就只会影响到自己到根的这一条链，考虑树链剖分，发现最多修改 \log n 条链。

对于重链上每一个点，可以设 G(x) 为 x 的轻儿子的信息，F(x) 为 x 为根的信息，然后随便维护，注意跳链时要修改G(fa[top[x]])就好了。

例题四

给出一棵树，每个点有点权。有2种操作，形如

$2、Query\ k

询问有多少非空连通子树，满足其点权的异或值恰好为k。 输出对10007取模。

n, Q ≤ 30000, 0 ≤ A_i , y, k < 128

做法

前置：fwt

思路就是对于每个点，先 fwt 过去，用数据结构维护信息，然后 fwt 回来，然后发现从重链上相邻两个节点的转移可以用含 G(x) 的矩阵表示，然后线段树维护矩阵即可。

3.5 树上同色连通块维护问题

考虑一棵黑白两色的树，对于每个极大的同色连通块，其最浅点，即整个连通块的 LCA 是唯一的，且可以通过树链剖分或者 LCT 快速地找到，即求某个点到其最近异色祖先路径上的倒数第二个点。我们不妨把信息维护在这个最浅点处。

最浅点的颜色修改时，连通块的形状会有较大变化——原本与其同色的儿子要变成异色，而原本异色的儿子变成同色。如果直接维护“点x子树内与x同色的连通块信息”，要 花费 O(儿子个数) 的时间。

解决的办法是在每个节点上同时记录两种颜色的信息，即如果一个点是黑色/白色时， 以它为最浅点的该种颜色连通块的信息。这样修改它的颜色时，它本身的信息不需要修改， 只要在父节点处添加/删除这个点的信息就可以了。

如果颜色数不是两种，而是一个较小的常数k，可以维护 k 个结构，第 i 个结构中把第 i 种颜色当作黑色，其余颜色当作白色进行处理。这样可以以复杂度乘 k 的代价支持多种颜色的 维护。

例题五

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

1、询问点u所在同色连通块的大小。

2、翻转点u的颜色，即黑色变白色，白色变黑色。

n, q ≤ 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) 。