跳转至

树上启发式合并 DSU on Tree

启发式合并

什么是启发式合并呢？并查集的按秩合并会吧？如果会，那么你就已经会了启发式合并。

启发式合并是指基于经验和直观感觉得到的神秘优化。并查集的按秩合并时，我们会把“小集合”合并进“大集合”。

因为我们在正常情况下，会把集合大小类比为树高（不完全相同），那么树高小的合并进树高大的显然能降低树的高度，得以优化复杂度。

这种神秘优化就是启发式合并！

树上启发式合并

树上启发式合并就是启发式合并（人类智慧 bushi）上树了！

树上启发式合并是一种人类智慧优化的暴力算法，复杂度（只针对该算法）通常为 \(O(n\log n)\) ，比同为暴力的树上莫队 \(O(n \sqrt n)\) 还要优秀。

但是，树上启发式合并的使用要满足两个条件！

树上启发式合并的使用条件
  1. 只有询问，没有修改。
  2. 对于一个节点 \(u\)，节点的答案能由其所有子节点中任意一个子节点 \(v\) 推出，且询问只和子树有关。

以树上数颜色为例：

U41492 树上数颜色

给一棵根为 \(1\) 的树，每次询问子树颜色种类数

而对于所有数据，有 \(1\leq m,c[i]\leq n\leq 10^5\)

对于暴力，我们会对每一个点，扫描整个树来统计答案。

而对于启发式合并，我们先做轻重链剖分，然后自下而上走节点。

对于每个节点，我们先将轻儿子的答案 dfs 出来，清空得到的答案（腾空间），然后将重儿子答案 dfs 出来，不清空，回溯到本节点，通过重子树的答案推理得到本节点的答案，并同时将询问答案记录下来。

dfs 结束，答案也就全部得出，可以直接回答了。

代码：我蓝得写，大家看OI-wiki上的吧，我口胡一下。

对于树上数颜色，我们用 ct[x] 记录 \(x\) 颜色出现的个数，tot 为 dfs 时的实时答案，add/del(int x) 和莫队算法一致。

我们轻重链剖分完后，对于 dfs(...)，(...) 中我们记录：

\(x\) : 当前节点

\(f\) : 父亲节点

\(W\) : 当前节点是否是重儿子（重儿子就保留，否则就在最后情况答案）

先把轻儿子跑一遍 dfs，然后跑一遍重儿子。

然后将轻子树的所有颜色暴力加入 ct[] 中，之后将答案记录下来。

如果是轻儿子，将所有的本节点产生的所有贡献通过 del 减掉。

本题就做完了。

其他题目的 dfs 中，操作不像本题 add/sub 一样简单。

往往需要暴力子树递归，用递归的方式算轻儿子中的贡献。

注意

暴力子树递归时，我们只不进入操作节点的重儿子，而轻儿子下的重儿子也是要产生贡献的。

所以要单独记录本节点的重儿子的序号，在递归时不访问。

代码

实现 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
int dep[N], son[N], siz[N];
void dfs()
{ // 重链剖分
    dep[x] = dep[f] + 1;
    siz[x] = 1;
    for (int i = head[x]; ~i; i = nxt[i])
    {
        int y = to[i];
        if (y ^ f)
        {
            dfs(y, x);
            siz[x] += siz[y];
            if (!son[x] || siz[son[x]] < siz[y]) son[x] = y;
        }
    }
}
void add(int x, int f, int s)
{ // 加入贡献(本节点，父节点，最初节点的重儿子)
    ct[a[x]]++;
    //<--- 一些判断操作（例如最大值判断，如果答案变得更大则更新答案）
    for (int i = head[x]; ~i; i = nxt[i])
    {
        int y = to[i];
        if (y ^ s && y ^ f)
            add(y, x, s); // 不进入（最初的节点的）重儿子和父节点
    }
}
void sub(int x, int f)
{
    ct[a[x]]--;
    for (int i = head[x]; ~i; i = nxt[i])
    {
        int y = to[i];
        if (y ^ f) sub(y, x);
    }
}
void dfs(int x, int f, bool W)
{
    for (int i = head[x]; ~i; i = nxt[i])
    { // 先轻儿子
        int y = to[i];
        if (y ^ f && y ^ son[x]) dfs(y, x, false);
    }
    if (son[x]) dfs(son[x], x, true); // 后重儿子
    add(x, f, son[x]);                // 计算轻子树贡献
    ans[x] = sum;                     // 记录答案
    if (!W)
        sub(x, f),
            sum = mx = 0; // 如果是轻儿子就减去贡献，同时将计算答案的变量清零
}

复杂度分析

空间：我们每次只针对一个子树研究，所以空间是 \(O(n)\) 的；

时间：因为我们分了轻重链，所有自上而下部分之后走重链的长度 \(O(\log n)\) 而每次进入节点扫轻子树近似看作 \(O(n)\) 的,所有时间复杂度是 \(O(n\log n)\) 的。

例题

CF1709E XOR Tree

U41492 树上数颜色

CF600E Lomsat gelral

CF375D Tree and Queries

CF1009F Dominant Indices

其中，CF1709E 和 CF600E 董晓算法在B站上有讲解，可以看一下。