算法简介：追加投资

启发式合并，我个人觉得和启发没什么关系，主要就是合并的方式，他用一种特殊的合并方式，达到看似暴力的复杂度，实则 $O(n\log n)$ 的复杂度完成问题，是一种相当奇特的算法。

且试身手：特许经营

普通启发式合并：百巧千奇

首先就是最最基本的启发式合并，上面的简介也说过，所谓启发式合并，重在合并方式。我们如何进行合并，可以使得复杂度降低呢？答案就是：从小到大合并。

为什么这样是正确的？确实，一眼看上去这和普通的合并方式并无区别，我们可以先考虑暴力。那么最最暴力的，随便找两个合并，单次合并的复杂度是 $O(n)$ ，一共要合并 $n-1$ 次，所以复杂度显然是 $O(n^2)$ 。那么如果我们从小到大合并，或者说把小的合并到大的里面会怎么样？

那么我们这边定义集合 $A, B$ ，且集合 $A$ 的大小小于 $B$ 。那么如果把 $A$ 合并入 $B$ ，就会发现，相对于 $A$ 来说，他的大小至少乘二。总共合并了 $n-1$ 次，那么均摊的来讲，这个 $A$ 只会被合并 $\log n$ 次。所有集合的大小加起来一共 $n$ ，总复杂度就是 $O(n\log n)$ 。

那么为什么从小合并到大是对的？我要是说把大的合并到小的，相对于小的不还是大小翻倍了吗？这就是因为我们单次合并的复杂度是集合大小的，如果是大合并到小，花费显而易见比小合并到大要多，不划算，复杂度也一定会大于我们上面小合并到大的做法。

例题讲解：妙显剑舞

这里就以一道启发式合并的模板题举例，ABC329F 这个题面自己看翻译就可以了。题目意思很简单，那么按照启发式合并的思想，我们每次把小的集合合并到大的，那么如何快速做到颜色的去重呢？那么就不难想到 STL set 。如果我们使用 set 可以非常完美的解决颜色球一样的问题，这样就需要在启发式合并的基础复杂度 $O(n\log n)$ 上面单独再乘上一个 $\log n$ ，总时间复杂度 $O(n\log^2 n)$ 搞定。下面是核心代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
while(Q--) { // 这是每一个操作的输入循环
    read(x, y);
    int flag = 0; // 这个记录了是否交换，但是是没用的
    if(a[x].size() > a[y].size()) { // 显然我们规定了从小到大合并，这里的交换就是为了保证小合并到大
        swap(a[x], a[y]); flag = 1;
    }
    for(auto &p : a[x]) { // 枚举，把小的合并到大的里面
        a[y].insert(p);
    }
    a[x].clear(); // 小的被倒完了
    printf("%d\n", a[y].size()); // 这就是答案
    // if(flag) swap(a[x], a[y]);
}

OK，那么显然大家应该都注意到了我弃用的 flag 变量，为什么交换完不需要交换回去呢？确实不用，我们交换的是盒子里的球，最终存放的结果都是 B 框里面放满了球，编号没有变，换了就是错的了。

树上启发式合并：酌盈剂虚

那么接下来就是树上启发式合并，一样地，树上启发式合并也是遵循小的合并到大的原则，一般来讲都是让你离线处理一些子树信息。一想到大合并到小，一定是指的儿子之间子树的大小关系，那么我们就可以考虑优先合并轻儿子，再考虑合并重儿子。这个过程有点复杂，我们来一道例题顺便看看。

例题讲解：漫掷万镒

题目传送门 - CF600E

题目意思很简单。统计一个子树中出现次数最多的那些数的和。首先我们一定可以想到就像刚刚一样，开一个 set 去解决问题。但是说，这样的复杂度其实是不够优秀的，我们考虑能不能去掉这个 set 。

我们首先考虑轻重儿子的优先合并关系，显而易见的轻儿子的合并优先于重儿子，我们可以暴力的将所有轻儿子优先处理完以后处理重儿子，这是候就要考虑合并计算这颗子树的总答案，我们直接大力把他们全部合并，合并的过程就是把轻儿子移除，我们需要的时候再把他们加入回来，就可以保证答案正确。这样的话我们就免除了 set 的 log 复杂度，可以在单 log 的复杂度完成问题。

代码也很简单的就可以完成。

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
inline void Insert(int u, int fa, int v) {
    cnt[c[u]] += v;
    if(cnt[c[u]] > mx) {
        mx = cnt[c[u]];
        sum = c[u];
    }
    else if(cnt[c[u]] == mx){
        sum += c[u];
    } 
    for(int i = G.head(u); i; i = G.nt(i)) {
        int p = G.to(i);
        if(p == fa || vis[p]) continue;
        Insert(p, u, v);
    }
}

// dsu on tree
inline void Sol(int u, int fa, int flag) {
    for(int i = G.head(u); i; i = G.nt(i)) {
        int v = G.to(i);
        if(v == fa) continue;
        if(v == son[u]) continue;   
        Sol(v, u, 0);
    }
    if(son[u] != 0) {
        Sol(son[u], u, 1);
        vis[son[u]] = 1;
    }
    Insert(u, fa, 1);
    ans[u] = sum;
    if(son[u] != 0) vis[son[u]] = 0;
    if(!flag) {
        Insert(u, fa, -1);
        mx = sum = 0;
    }
}

算法实战：物超所值

查看相关算法标签喵！