点分治总结

一直想总结点分治的一些技巧。结果因为各种原因鸽了。现在补一个。

点分治与点分树

点分治（centroid decomposition）算法的大致流程是，对于$n$个点无根树$T$：

• 首先找到$T$的一个重心$c$，然后处理与重心有关的信息。
• 然后删掉重心，那么$T$将划分为若干个更小的连通块$T_1,\cdots,T_k$，对于每个连通块递归进行上述算法。

如果我们把$T_1,\cdots,T_k$的重心当作$c$的$k$个儿子，递归构建，这样可以建出一棵新的树$T_C$，我们称之为点分树（centroid decomposition tree）。

点分树的重要性质：由于$c$是$T$的重心，因此$2|T_i|\le |T|$。也就是说每往下走一层，连通块大小至少减半。因此点分树的树高是$O(\log n)$的。

那么点分治和点分树适用于处理什么类型的问题呢？

路径问题

需要求出满足某种条件的路径条数，或者满足某种条件的路径权值和。那么我们可以在点分治的过程中，将路径按照

• 经过重心（或者以重心为端点）
• 不经过重心

分类。如果一条路径不经过重心， 它一定在某个更小的连通块中，这类路径我们递归处理。因此在当前状态下我们只用处理经过重心的路径。也就是说，点分治将任意路径转化为了经过定点的路径。如果我们把重心作为连通块的根结点，那么点分治还可以把无根树路径转化为有根树上经过根结点的路径。

点集问题

有时我们需要求出，满足某种条件的连通块（点集）的个数。这个条件通常是可以转化为点与点之间的条件的。那么我们可以钦定在连通块（点集）深度最低的点上统计这个连通块的信息。

具体地，我们仍然考虑点分治。那么我们将连通块分成

• 经过重心（如果是点集，那么就是跨过重心）
• 不经过重心

两种。以重心为根，那么相当于我们要求的就是包含根结点的连通块的信息。

其他类型

事实上，点分治可以运用的场景还有很多。但它的主要作用就是钦定一个点，把问题转化为和这个点有关的信息处理。

记号

为了方便表述，我们在这里定义一些记号。

一棵无根树$T=(V,E)$，其中$V$是点集，$E$是边集。$(u,v)$表示一条无向边。

$P(u,v)$表示$u$到$v$的一条无向路径，$P(u \to v)$表示$u$到$v$的有向路径。

$T$的点分树是$T_C$。

以结点$u$为重心的点分树连通块记作$C_u$。$u$在点分树上的父亲是$F_u$。

捉迷藏

给你一棵树$n$个点的树，支持$m$个询问：

1. 改变一个点的颜色（黑白）。
2. 求黑点构成的虚树的直径。

$n\le 10^5,m\le 5\times 10^5$。

如果没有修改操作，那么可以点分治或者直接树形 DP 求。

我们从修改操作的角度考虑。建出点分树。那么修改一个点的颜色，会影响包含这个点的连通块的信息。而点分树树高是$O(\log n)$的，因此包含这个点的点分树连通块只有$O(\log n)$个。那么我们只需要思考，如果使用点分树连通块维护信息即可。

一条路径（直径），一定经过某个点分树连通块的重心。同时，一条路径可以拆分成从重心出发的两条路径，分别通往两个不同的子连通块。

因此对于点$u$，我们使用一个堆$S_u$表示$C_u$中的黑点到$F_u$的直径（不管$F_u$是不是黑点）。然后我们用另一个堆$P_u$维护$u$的点分树儿子$v$，且$v$是黑点的$S_v$的堆顶。这样，$P_u$的最大值和次大值就是$C_u$中经过$u$的直径。然后对于每个点，我们把它的直径都放在一个大的堆$A$中。那么$A$的堆顶就是整颗树的直径。

对于一次修改$u$的颜色，我们可能会涉及到包含$u$的点分树连通块的信息改变。那么我们暴力跳父亲，修改对应的$S_u,P_u$以及$A$即可。

那么我们维护的是带删除的堆。

还有一个小优化。就是我们预处理$d(i,j)$表示点$i$到$i$的点分树的$j$级父亲的距离。

总时间复杂度$O(n\log_2^2n+m\log_2n)$。

幻想乡战略游戏

给一棵$n$阶的点边带权的树$T$，初始时点权$d_u$为$0$。有$q$次操作，每次修改某个点的点权，要求在每次操作后询问

$$\min_{u\in T}\left\{ \sum_{v\in T}\text{dist}(u,v)d_v \right\}$$

其中$d_v$是点权，$\text{dist}$表示两点的距离（路径长度）。

特殊性质：每个点度数不超过$D$。

$n\le 10^5,D=20$。

设$f(u)=\sum_{v\in T}\text{dist}(u,v)d_v$。可以发现，$\text{dist}(u,v)d_v$在固定$v$的条件下，是一个树上凸函数，且以$v$为顶点。

这里的树上凸函数是指对于每条路径$P(x,y)$上的点，$\text{dist}(u,v)d_v$是一个凸函数。实际上在本题中它是一个绝对值函数，但也满足凸函数的性质。

因此若干个凸函数的和也是凸函数。也就是说$f(u)$也是树上凸函数。那么我们就可以使用类似找重心的算法来求$f(u)$。假设当前结点是$u$，那么我们枚举$u$在原树上的邻居$v$，然后计算$f(v)$。如果$f(v)<f(u)$，那么我们就跳到$u$的儿子连通块中包含$v$的那个的重心上，递归下去。

因此现在的问题是，如何在递归的过程中快速计算$f(u)$。

不方便直接维护$f(u)$，我们就维护它的贡献和。当我们从$u$跳到$u'$——子连通块的重心的时候，其他连通块就可以缩点，然后接在$u'$的某个叶结点上。因此我们可以统计其他连通块的贡献和，然后把点权和加到这个叶子结点上。因此我们只需要维护$F(u)=\sum_{v\in C_u}\text{dist}(u,v)d_v$即可，当然还有一些其他需要维护的，比如$F_2(u)=\sum_{v\in C_u}\text{dist}(F_u,v)d_v$之类的，但这都是小问题。

在修改的时候，这些可以暴力跳父亲修改。

时间复杂度$O(n\log ^2n+q\log n(\log n+D))$。

SCOI Online 树

是 SCOI2018 的题。

给出一棵$n$个点的树，第$i$个点有权值$a_i$，现在需要支持$m$次操作：

• 第一种操作格式为 “1$u$”，表示询问从$u$出发的简单路径，经过的点权值之和的最大值；
• 第二种操作格式为 “2$u$$v$”，表示将$a_u$修改为$v$。

$1\le n\le 10^5,1\le m\le 10^5,|a_i|,|v|\le 10^4$。

建出点分树。从$u$出发的路径，一定是经过点分树上$u$的某个父亲$p$，然后延伸向另一个与$u$不同的连通块。修改一个点的权值，会修改若干条路径。不过我们已经将问题转化为了点分树连通块里以重心为端点的路径信息问题——也就是定了根。那么修改一个点权，就会修改一个子树的路径的权值。自然想到线段树维护子树 max。再用一个堆维护子连通块的 max 集合即可。修改的时候暴力跳父亲修改即可。

时间复杂度$O((n+m)\log ^2n)$。

Giant Penguin

定义$k$仙人掌为一个简单无向连通图$G$，满足其中的任意一个点都被包含在$\le k$个简单环中。

给你一个$n$个点$m$条边的$k$仙人掌，操作：

1. 标记一个点；
2. 问距离点$u$最近的被标记的点的距离。

$n\le 10^5,m\le 2\times 10^5,k\le 10$。

考虑在$k$仙人掌上点分治。我们先搞一棵生成树$T$。对于当前连通块，我们确定一个点为重心，那么至多有$k$条非边是连接在子连通块之间的。而且我们可以快速找出这$k$条边。那么在删除的时候，我们同时删除重心和这$k$条边，就可以把其他子连通块割裂开来。这样就可以建出$k$仙人掌的点分树。我们称这$k$条边的端点集合是$u$的关键点。

距离$u$最近的被标记的点，要么经过$u$的点分树上某个父亲，要么经过某个父亲的关键点。因此我们可以对于每个点预处理$f(u,i,j)$表示$u$到点分树的$i$级父亲的第$j$个关键点的距离。然后维护$d(u,j)$表示距离$u$的第$j$个关键点的最小距离（不妨设为$d(u,0)=u$）。因为我们只会标记而不需要撤消，因此不需要维护堆。这样一通更新即可。

时间复杂度$O((n+m)k\log_2n)$。

Airplane Cliques

给你一棵$n$个点无根树$T=(V,E)$。给出常量$x$。

称一个点集$S$是好的，当前仅当其中任意两个点距离不超过$x$（边长为$1$）。

求出大小为$1,2,\cdots,n$的好的集合的个数。

$1\le n\le 3\times 10^5$，对$998244353$取模。

任意两个点距离不超过$x$，等价于给树定根后：

• 设$u$是$S$中深度最深的结点；
• 对于任意$v\in S$，$v$到$u$的距离不超过$x$。

因此我们可以把$S$放在$S$深度最深的点处统计方案数。

为了防止多个深度相同的最深点重复统计，我们按序给结点标号来统计。也就是说我们给树定根，按照 BFS 序

• 标记一个结点$u$；
• 统计有多少个标记过的结点$v$到$u$的距离不超过$x$。

由于是 BFS 序，这样就不用考虑深度的问题了。因此给树定根只是为了确定 BFS 序。实际上这个统计是可以看作在无根树上进行的。

至于统计的部分，我们可以维护点分树连通块中，到重心的标记过的点的距离集合。那么我们查询就暴力跳重心，二分统计即可（要减掉在自己连通块部分的贡献）。可以使用点分树 + 树状数组统计。

这样统计完之后，设$a_u$表示$u$的统计结果。设$f_i$表示大小为$i$的好的集合的个数。显然$a_u$对$f_i$的贡献是$\binom{a_u}{i}$。不防设$c_i=\sum_{j=1}^n[a_j=i]$。则$c_i$对$f_j$的贡献就是$\binom{i}{j}c_i$。因此

$$f_j=\sum_{i=1}^n\binom{i}{j}c_i$$

可以得到$j!f_j=\sum_{i=1}^nc_i i!\frac{1}{(i-j)!}$。这是一个卷积的形式，可以简单 reverse 一下就能多项式计算了。

因此总时间复杂度$O(n\log^2n)$。