基于变换合并的树上动态 DP 的链分治算法 & SDOI2017 切树游戏（cut）解题报告

最近听说 SDOI2017 R2 某题可以用我论文中的“基于链的分治优化树上动态 DP”的方法 A 掉……我很开心啊……

因此我把这道题出到了校内训练中……

在出题之前，肯定是要去把这题先做一遍的……然后，我发现我弄出了一些新的东西……！

题意简述

给出一棵无根树 $T$ ，节点从 $1$ 到 $n$ 编号，点 $i$ 的权值为 $v_{i}$ 。定义一棵树的权值为树中所有点的权值异或起来的结果。

你想要在树上玩一个游戏。你会做 $m$ 次以下两种操作：

C x y：将 $v_{x}$ 修改为 $y$ 。
Q k：询问 $T$ 有多少棵非空的连通子树，满足这棵子树的权值为 $k$ 。输出模 $10007$ 。

数据范围： $n, m \leq 30000$ ， $0 \leq v_{i}, y, k < 128$ 。

时空限制：2s、128MB。

算法讨论

如果只有一次询问，非常容易想到暴力 DP。先转有根树。在全局记录答案数组 $a n s (k)$ 表示权值为 $k$ 的子树个数。对每个点 $i$ 记录 $f (i, k)$ 表示子树中深度最小的点为 $i$ 且子树权值为 $k$ 的连通子树个数。记录 $g (i, j, k)$ 表示子树中深度最小的点为 $i$ 且所有其他的节点都在 $i$ 的前 $j$ 个子节点的子树中的连通子树个数。那么我们就有以下方程（设 $C h (i)$ 为 $i$ 的子节点列表）：

$g (i, 0, k) = [k = v_{i}]$
$g (i, j, k) = \sum_{t = 0}^{127} g (i, j - 1, t) \times (f (C h (i)_{j}, k \oplus t) + [k \oplus t = 0])$
$f (i, k) = g (i, | C h (i) |, k)$
$a n s (k) = \sum_{i = 1}^{n} f (i, k)$

总时间复杂度为 $O (n m \times 128^{2})$ 。

接下来可以注意到第 2 个式子是一个“异或卷积”的形式，不难想到使用 FWT 可以优化到 $O (128 \log 128)$ 。然后注意到 FWT 之后，加法和乘法都可以直接按位相加，因此可以在一开始就将所有数组 FWT，运算过程中全部使用 FWT 之后的数组，最后再将 $a n s (*)$ 数组 FWT 回去即可。这样就可以去掉一个 $\log 128$ 。时间复杂度为 $O ((n + \log 128) \times 128)$ 。

再接下来就是优化修改复杂度了。~~看过我论文或做过 BZOJ 4712 的同学~~容易想到使用链分治维护树上动态 DP。首先将树进行轻重链剖分，然后按照重链构成的树的顺序进行 DP。如果这样以后每一条重链上的转移可以高效维护、支持修改，那么每次修改点 $p$ 之后，我们就可以高效地更新点 $p$ 到根的 $O (\log n)$ 条重链的信息即可。

首先 $a n s (k)$ 是全局变量，不好维护。那么可以不记录 $a n s (*)$ ，而是记录 $h (i, k)$ 表示 $i$ 子树中的 $f (i, k)$ 的和，那么这样整个 DP 就有子树的阶段性了。

可以发现 $f (i, k)$ 就是先将 $g (i, 0, *)$ 和所有子节点 $p$ 的 $f (p, k) + [k = 0]$ 全部卷积起来的值。即如果设 $F_{i} (z)$ 表示 $f (i, *)$ 这一数组的生成函数，那么可以得出 $F_{i} (z) = z^{v_{i}} \prod_{p \in C h (i)} (F_{p} (z) + z^{0})$ 这里的卷积定义为异或卷积。那么对于一条重链上的每一个点 $i$ ，我们只需要将 $i$ 的所有轻儿子 $l p$ 的 $F_{l p} (z) + z^{0}$ 全部卷积起来，这样就考虑了所有轻儿子的子树中的贡献，设这个卷积的结果为 $L F_{i} (z)$ 。同样对于每个点我们记录 $L H_{i} (z)$ 表示这个点的每个轻儿子的 $H_{l p} (z)$ 之和（这里 $H_{i} (z)$ 的定义类似 $F_{i} (z)$ ，只不过是对 $h (i, *)$ 定义的）。每个点的轻边的信息和可以用线段树维护来支持高效修改。

Claris 大神说这里信息可减因此不用线段树，但我觉得这里的 $L F_{i} (z)$ 的信息相减需要做除法，如果出现 10007 的倍数则没有逆元，无法相除，因此我仍然采用线段树维护。

注意到上述算法只要求我们能求出 $F_{重链顶} (z)$ 和 $H_{重链顶} (z)$ ，就可以维护父亲重链的信息或答案了。因此现在只需要考虑所有过当前重链的子树。在这里我们有如下两种截然不同的思路。

基于维护序列信息的算法

论文中提到的方法是转化为序列上的问题，然后使用线段树维护。由于连通子树和重链的交一定也是一段连续的链，那么我们显然就可以像最大子段和问题那样，记录 $D_{a, b} (z)$ 表示 $a = [$ 左端点在连通子树中 $]$ 、 $b = [$ 右端点在连通子树中 $]$ 的方案数。这个算法将修改复杂度优化为 $O (128 \log^{2} n + 128 \log 128)$ ，已经可以通过本题了。

但是这个算法有一定的问题：首先它具有较大的常数因子，运行时间较慢。其次，这个算法仍然利用了具体题目的性质——连通子树和重链的交还是链。而并非所有的题都有这样的性质。最后，由于要不重不漏地计数，代码细节繁多，十分难写。

基于变换合并的算法

对于一条重链，设重链上的点按深度从小到大排序后为 $p_{1}, p_{2}, . . ., p_{c}$ ，那么我们可以得出以下方程：

$F_{p_{c}} (z) = H_{p_{c}} (z) = z^{v_{p_{c}}}$ （因为 $p_{c}$ 没有子节点）
$F_{p_{i}} (z) = L P_{p_{i}} (z) \times (F_{p_{i + 1}} (z) + z^{0}) \times z^{v_{p_{i}}}$
$H_{p_{i}} (z) = H_{p_{i + 1}} (z) + F_{p_{i}} (z)$

而我们所需要求的只有 $F_{p_{1}} (z)$ 和 $H_{p_{1}} (z)$ 。

可以观察到上面这个式子中，向量 $(F_{p_{i + 1}} (z), H_{p_{i + 1}} (z), z^{0})$ 是通过一个线性变换得到向量 $(F_{p_{i}} (z), H_{p_{i}} (z), z^{0})$ ，具体地来说是右乘上这样一个矩阵：

$M_{i} = (\begin{matrix} L F_{p_{i}} z \times z^{v_{p_{i}}} & L F_{p_{i}} z \times z^{v_{p_{i}}} & 0 \\ 0 & 1 & 0 \\ L F_{p_{i}} z \times z^{v_{p_{i}}} & L H_{p_{i}} + L F_{p_{i}} z \times z^{v_{p_{i}}} & 1 \end{matrix})$

而矩阵乘法是满足结合律的，也就是说，我们只需要用线段树支持单点修改某个矩阵 $M_{i}$ 、维护矩阵的积，我们就可以高效地求出我们所需要的向量 $(F_{p_{1}} (z), H_{p_{1}} (z), 1)$ 。而这是容易做到的，因此这个算法是完全可行的。这样，这个算法也将修改复杂度优化为了 $O (128 \log^{2} n + 128 \log 128)$ ，可以通过本题。

简单优化这个算法的常数。注意到形如 $(\begin{matrix} \underset{―}{a} & \underset{―}{b} & 0 \\ 0 & 1 & 0 \\ \underset{―}{c} & \underset{―}{d} & 1 \end{matrix})$ 的矩阵乘法对这个形式封闭，因为 $(\begin{matrix} \underset{―}{a_{1}} & \underset{―}{b_{1}} & 0 \\ 0 & 1 & 0 \\ \underset{―}{c_{1}} & \underset{―}{d_{1}} & 1 \end{matrix}) \times (\begin{matrix} \underset{―}{a_{2}} & \underset{―}{b_{2}} & 0 \\ 0 & 1 & 0 \\ \underset{―}{c_{2}} & \underset{―}{d_{2}} & 1 \end{matrix}) = (\begin{matrix} \underset{―}{a_{1} a_{2}} & \underset{―}{b_{1} + a_{1} b_{2}} & 0 \\ 0 & 1 & 0 \\ \underset{―}{a_{2} c_{1} + c_{2}} & \underset{―}{b_{2} c_{1} + d_{1} + d_{2}} & 1 \end{matrix})$

因此我们只需要对每个矩阵维护 $a, b, c, d$ 四个变量即可。同时可以直接用等号右边的形式来计算矩阵乘法，这样就只需要做 $4$ 次而不是 $27$ 次生成函数乘法了，常数大大减小了。

比较与扩展

这两个算法的时间复杂度相同，并且都可以扩展到询问某一个有根树子树的信息——只需要对那一条重链询问一下信息和/变换和即可。

我们来审视一下后一个算法。首先，这个算法基于的是直接对这个 DP 本身进行优化这样一种思想，而不是通过分析具体题目的性质进行处理，因此这种算法具有更高的通用性。其次，由于这个算法是直接对这个 DP 本身进行优化，因此正确性显然，细节也要少于论文中介绍的在区间中维护 $D_{a, b} (z)$ 信息的方法（维护 $D_{a, b} (z)$ 这个方法必须严格分类，因此细节繁多，常数也较大）。因此这个算法比前一个的算法更加优秀。

然而，事实上这个算法同样利用了题目的一些性质——这题是计数类问题，而且转移是线性变换，因此可以用矩阵来维护，而矩阵恰恰是一种可以合并的变换。那么对于其他的题目，是否也能用这种基于变换合并的算法呢？

BZOJ 4712 加强版（不保证修改不降）

这是一道在论文中有提到的题目。论文中介绍的算法正是一种基于标记合并的算法，其标记为 $t r a n s_{a, b} (x) = min (a, x + b)$ 并且对加法封闭。这个算法的常数十分优秀。

树上动态最大权独立集问题

这同样是一道在论文中有提到的题目。论文中介绍的是使用线段树维护序列上信息的方法。

考虑新的思路。记录 $f (i)$ 表示所有点都在 $i$ 子树中的最大权独立集的权值（以下简称答案）， $g (i)$ 表示所有点都在 $i$ 子树中且独立集不包括点 $i$ 的答案；同样记录 $L f (i)$ 、 $L g (i)$ 表示所有轻儿子的 $f (l p)$ 或 $g (l p)$ 的和。

首先写出 $p_{i}$ 关于 $p_{i + 1}$ 的转移：

$g (p_{i}) = L f (p_{i}) + f (p_{i + 1})$
$f (p_{i}) = max (g (p_{i}), v_{i} + L g (p_{i}) + g_{(} p_{i + 1})$

考虑对这些 $g_{p_{i}}$ 、 $f_{p_{i}}$ 定义新的加法和乘法运算：其中“加法” $a \oplus b$ 定义为 $max (a, b)$ 、“乘法” $a \otimes b$ 定义为 $a + b$ ——根据加法分类、乘法分步的原理定义。那么转移方程可以写成这样：

$g (p_{i}) = L f (p_{i}) \otimes f (p_{i + 1})$
$f (p_{i}) = L f (p_{i}) \otimes f (p_{i + 1}) \oplus v_{i} \otimes L g (p_{i}) \otimes g_{(} p_{i + 1})$ // 这里将 $g (p_{i})$ 代入了

这样，我们的转移就同样是“线性变换”，可以用矩阵来维护矩阵乘法了。算法的正确性可以用将这种新定义运算的矩阵乘法展开后证明，也可以将这种算法类比为 Floyd 求最短路来理解——它和 Floyd 的实现其实是一样的。

神奇的子图

这就是论文题……

首先考虑树上的算法。记录 $f (i, k)$ 表示所有点都在 $i$ 中且 $i$ 的点度为 $k$ 时的连通子图最大权值和，记录 $g (i)$ 表示 $i$ 子树中所有点 $j$ 的 $max f (j, *)$ 。转移的时候， $f (i, *)$ 是对子节点跑重量为 $1$ 、价值为 $max f (p, k < K)$ 的背包，同时更新 $g (i)$ 。

可以注意到，背包可以写成卷积的形式，而卷积可以写成矩阵乘法的形式，因此使用矩阵来表示变换是完全可行的。维护向量 $(f (p_{i}, 0), f (p_{i}, 1), . . ., f (p_{i}, k), g (p_{i}), 1)$ ，这样不难写出转移矩阵，就可以进行转移了。使用线段树维护即可做到和论文中相同的复杂度。同样，结合圆方树可以得到本题的另一个满分算法，复杂度相同。

这个算法的细节比原来的算法要少非常多，常数也小一些。

UOJ 268

终于不是论文中提到的题目了……

题意经过简化后变成这样：给出一棵树，每个点有 $a_{i}, b_{i}$ 两个权值，定义一条链 $(x, y)$ 的权值为链上所有点的 $a_{i}$ 加上 $b_{LCA (x, y)}$ 。要求单点修改 $a_{i}$ 、链上修改 $b_{i}$ （修改都是加一个数或减一个数），动态维护权值最大的链。

可以类比《神奇的子图》记录状态 $f (i, k \in {0, 1, 2})$ 、 $g (i)$ ，意义和转移类似《神奇的子图》，只是 $f (i, *)$ 更新 $g (i)$ 时要加上 $b_{i}$ 。单点修改 $a_{i}$ 容易支持，考虑如何支持链上修改 $b_{i}$ 。不妨将 $b_{i}$ 差分，即设 $b_{i}^{'} = b_{i} - b_{f a (i)}$ ，那么我们同样可以用 $b_{i}^{'}$ 写出转移方程，并且链上修改变成了单点修改，易于维护。

转化为单点修改后，虽然要进行 $4$ 个节点的单点修改，但单点修改的常数小于链上修改，因此这个算法常数优于之前的算法。

神奇的简单路径

又是论文中的题了……

题意简述：给出一张图，保证每个点双 $\leq 8$ ，每次修改点权，或询问两点之间最长简单路径，或询问全局最长简单路径。

如果只有全局最长简单路径，那么就是《神奇的子图》的弱化版。现在考虑第一个询问。这种询问相当于在圆方树上做链上询问。如果是暴力的话，那么就是沿着链一个一个点 DP 上来。这种链上的 DP 显然也可以写成变换的形式，那么我们也只需要维护这条链上的变换和即可，具体实现同样用矩阵，复杂度和原算法相同。

要注意的是一个一个 DP 上来时有向上的一段和向下的一段，因此线段树中维护矩阵的积时也要维护一正一反两种信息。

总结

基于变换合并的树上动态 DP 算法，完全地采用了对 DP 本身进行优化的思想，思路较于一般的树上动态 DP 算法思路更加直观、正确性更加显然。它不仅可以通用地解决之前所有的问题，还可以获得更小的思维难度、更小的代码难度和更快的运行速度，是论文中介绍的原算法的一个很大的改进。

当然，这个算法还有一些局限性。希望大家能和我分享关于这方面的研究，希望在我们的共同努力下能有更多更好的算法出现。

immortalCO的博客

博客