浅谈树上启发式合并（dsu on tree）

这就是一个优雅的暴力。

引入

我们来看一道题：

给出一棵树，每个节点都有一个颜色。

查询一棵树中以每个节点为根的子树中颜色种类的多少。

因为子树之间会互相影响，我们就只能对于每个节点求一次，这时候暴力的时间复杂度就是 $O(N^2)$ 的。

我们可以用 $dsuontree$ 来达到 $O(n\cdot lo{g}_n)$ 的时间复杂度。

思路

我们先来看下暴力的代码：

void update(int x, int fa, int flag) {
    num[color[x]] += flag;
    if (num[color[x]] == 0 && flag == -1)
        cnt--;
    if (num[color[x]] == 1 && flag == 1)
        cnt++;
    for (int i = last[x]; i; i = E[i].next)
        if (E[i].to != fa)
            update(E[i].to, x, flag);
}
void dfs(int r, int fa) {// 求子树r中的信息, fa为r的父亲
    for (int i = last[r]; i; i = E[i].next) // 遍历r的邻接点
        if (E[i].to != fa)
            dfs(E[i].to, r);
    update(r, fa, 1);// updata就是用来求以r为根的子树的颜色种类个数
    ans[r] = cnt;
    update(r, fa, -1);// 清空数组
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

我们来想想如何优化

我们知道，一个节点可以由多个儿子的信息得来，但是儿子的答案又不能互相影响，于是我们就可以保留一个儿子的答案用到我们这个子树中。

为了更快，我们肯定是选择儿子中最大的那个来继承。

于是我们就可以得到代码。

void dfs(int x, int fa) {
    for (int i = last[x]; i; i = E[i].next)
        if (E[i].to != son[x] && E[i].to != fa) {
            dfs(E[i].to, x);// 我们先把除了需要继承的儿子的答案求出来
            update(tv, x, -1);// 因为不继承这个儿子，所以就清空数组
        }
    if (son[x])
        dfs(son[x], x);// 求出需要继承的儿子，此时就不清空数组
    num[color[x]]++;//注意！！！一定要加上自己这个节点！！！
    if (num[color[x]] == 1)
        cnt++;
    for (int i = last[x]; i; i = E[i].next){
        if (E[i].to != son[x] && E[i].to != fa)
            update(E[i].to, x, 1);//因为我们除了需要继承的儿子都没有加进答案里面，所以需要加入答案
        ans[x] = cnt;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

我们来分析一下时间复杂度。

因为这实际上很像树链剖分，于是我们就将轻边和重链引入进来。

我们可以发现，一个子树会被 $updata$ 到的次数就是从该节点到根的路径中有多少轻边。

对于每个点，假设它和它的父亲的连边为轻边，则他的父亲的子树大小一定是该节点的两倍，所以可以证明一个节点到根的路径最多有 $lo{g}_n$ 条轻边，所以每个节点最多被 $updata$ 到 $lo{g}_n$ 次，一共有 $n$ 个点，所以时间复杂度就是 $O(n\cdot lo{g}_n)$ 。