静态链分治和树上启发式合并

静态链分治 (DSU on Tree) 和树上启发式合并 (Heuristic Merge on Tree) 是简洁有力的处理树上问题的工具，而代价仅为将复杂度乘上 $O(\log n)$。在处理询问时，要求询问离线。

很多人把静态链分治和树上启发式合并混为一谈，但它们其实是截然不同的算法。大家常见并称之为“树上启发式合并”的算法其实是静态链分治。

静态链分治

例题

给定一棵有根树，每个节点上都有一种颜色。回答所有子树中不同颜色的个数。

这是一道老生常谈的经典题，可以用线段树合并 (复杂度 $O(n\log n)$) 和树分块 (复杂度 $O(n\sqrt n)$，又称 树上莫队) 等方法解决。但静态链分治也可以解决此题，而且常数较小 (我自己写的静态链分治比线段树合并慢)。

利用一个数组 $\text{cnt}$ 来记录每种颜色的出现次数。对树进行重链剖分，处理节点 $i$ 时：

• 先处理所有轻儿子，得到轻儿子子树中所有节点的答案，并在处理完每个轻儿子后清空 $\text{cnt}$。
• 然后处理重儿子，得到重儿子子树中所有节点的答案。处理完后不清空 $\text{cnt}$。
• 最后再遍历轻儿子。至此 $i$ 子树中的所有节点都计入了 $\text{cnt}$，我们得到了 $i$ 的答案。

复杂度证明

静态链分治中有四个产生复杂度的过程：处理轻儿子、清空轻儿子、处理重儿子、遍历轻儿子 (和本身)。

其中，清空轻儿子和遍历轻儿子的复杂度显然都是 $O(n\log n)$，因为每个点到根经过的轻边数都是 $O(\log n)$ 级的。

剩下的过程的复杂度为 $O(n)$。因此总复杂度为 $O(n\log n)$。

例题

Lomsat gelral
快乐游戏鸡

树上启发式合并

例题

给定一棵有根树，定义 $d(u,v)$ 为从 $u$ 到 $v$ 的简单路径包含的边数。令 $a=\operatorname{LCA}(u,v),f(u,v)=\gcd(d(u, a), d(a, v))$，求满足 $f(u,v)=i$ 的数对 $(u,v)$ 个数。

这是一道 UOJ 上的题 树上 GCD ，标算为 $O(n\sqrt n)$ 的点分治。但此题也可以用树上启发式合并做到几乎同样的复杂度，并且常数奇小，代码健康。

我们只要求出满足 $d\mid f(u,v)$ 的 $(u,v)$ 个数，就可以通过容斥或者莫比乌斯反演得到答案。我们设定一个分治界限 $B$，对于 $d\in[1,B]$，用动态规划求出满足 $i\mid f(u,v)$ 的点对数，复杂度为 $O(nB)$。

对于 $d\in [B+1,n]$，使用树上启发式合并。设 $dp_{i,j}$ 表示以 $i$ 节点为链顶，且长度为 $j$ 的链的个数。每次将 $i$ 的一个儿子的答案与 $i$ 的答案合并时，我们正常地启发式合并即可。

dp[i].push_back(1); // (i,fa[i]) 也是一个长度为 1 的链。这里 dp 数组是倒着的，dp[i][dp.size()-j] 表示长度为 j 的链的个数
if(dp[fa[i]].size() < dp[i].size())
    std::swap(dp[fa[i]], dp[i]); //在 C++11 以下的标准中，std::swap 不是 O(1) 的，必须使用 dp[fa[i]].swap(dp[i]) 来保证复杂度
for(int j = 0; j < (int)dp[i].size(); ++j)
    dp[fa[i]][dp[fa[i]].size() - j] += dp[i][dp[i].size() - j];

这一部分的复杂度为 $O(n\log n)$。

除了合并儿子与父亲的 $dp$ 数组，我们还要统计对答案的贡献：

dp[i].push_back(1);
if(dp[fa[i]].size() < dp[i].size())
    std::swap(dp[fa[i]], dp[i]);

int sz1 = dp[i].size(), sz2 = dp[fa[i]].size();
for(int d = B + 1; d <= sz1; ++d){
    long long int cnt1 = 0ll, cnt2 = 0ll;
    for(int j = d; j <= sz1; j += d)
        cnt1 += dp[i][sz1 - j];
    for(int j = d; j <= sz2; j += d)
        cnt2 += dp[fa[i]][sz2 - j];
    ans[d] += cnt1 * cnt2; // ans[d] 表示满足 d | f(u,v) 的 (u,v) 的个数
}

for(int j = 0; j < sz1; ++j)
    dp[fa[i]][sz2 - j] += dp[i][sz1 - j];

这一部分的复杂度较难分析。只有大于 $B$ 的 $\text{sz1}$ 才会对时间产生 $O(\text{sz2}\log\text{sz1})=O(n\log\text{sz1})$ 的贡献，而这种两个 $dp$ 数组的大小都大于 $B$ 的合并至多出现 $\dfrac{n}{B}$ 次，故复杂度为 $O\left(\dfrac{n^2\log n}{B}\right)$。

取 $B=\sqrt{n\log n}$ 即可得到理论最优复杂度 $O(n\sqrt{n\log n})$。实际上取 $B=10$ 最快，而且由于常数特别小卡不掉。

从这道题我们可以看出来，树上启发式合并本质上就是用启发式合并来优化树形 DP，是一种常数非常小的优秀算法，非常适合代替有根树上的点分治。它的缺陷就是启发式合并只能优化转移方程很简单的树形 DP，不如线段树合并用处广泛。

题外话

说到有根树点分治，不能不让人想起 购票。不过购票的所谓“分治”其实是 CDQ 分治，要求计算的并非树上路径，因而没法用树上启发式合并了。

评论