启发式合并（含一般式、树上启发式合并 例题）

启发式合并

（1）一般启发式合并

类似于并查集中的 按秩合并。

启发式合并 指的是，对于 两个集合 x 和 y 合并 的操作，每次 把元素个数更少的集合合并到元素个数更大的集合内，即：设 x 为元素更少的集合，那么就 把 x 合并到 y 内。

可以证明，启发式合并的时间复杂度 为：O(nlogn)。这可以从 贡献 的角度来理解，对于 每个元素，他所处的集合被合并 k 次，那么这个元素就被合并 k 次，但是 每次合并都会使得集合的大小乘以 2，那么 一个集合最多被合并 logn 次，所以 一个元素最多 被合并 logn 次，因此 n 个元素被合并的复杂度为 O(nlogn)。

例题：AcWing 2154. 梦幻布丁

题意：

给定 n 个数字，每个数字有一个权值代表其颜色 ai，现在有 m 次操作，操作的类型有 两种：

• 操作 1：询问当前 有多少个颜色段？（举个例子，比如 1 2 2 1 就是 3 个颜色段)
• 操作 2：将 x 颜色全部修改为颜色 y。
  $（限制条件：0<n，m<1e5+1、0<Ai，x，y<1e6）$

思路：

先想想 如何统计颜色段的数量，

初始时 进行统计的时候，可以 直接扫描一遍整个序列，每次看看 当前颜色是否和前一个一致，如 不一样，则 段数 ++，否则看下一段。

关键在于每次合并 两种颜色 的时候，如何维护段数，我们不妨 设它为 ans，

每次合并 将所有某种颜色 x 的布丁 全部 变成另一种颜色 y，其本质即为 将两者集合合并为同一类，

对于 颜色的段数，我们主要看的是 相邻两个布丁，

• 一开始如果颜色一致，之后变得不一致，那么段数就会 + 1，
• 如果 两者颜色前后都是一致或者不一致，那么 段数不变。

不过，段数 + 1 的那种情况是不可能存在的，因为我们每次是 将一种颜色的所有物品变成另一种颜色，所以说对于 相邻的布丁，如果 之前颜色一致，那么 之后颜色还是会一致。

因此，我们可以得出结论：每次合并两种颜色的时候，段数是不会增加的，只会减少或不变。

下图为 段数减少 2 的情况：（之前颜色不同，之后颜色相同，下图中我们将 红色变成蓝色）

具体做法：

• 枚举 所有颜色是 x 的布丁，对每个进行判断 其左右两边的布丁是不是即将变成的颜色 y，如 左颜色恰好是 y，那么当前布丁 变成 y 后，段数就会少 1，如 右颜色也是 y，那么 又会少 1。
• 每次 将 x 变成 y 的时候，我们 遍历颜色是 x 的所有布丁，判断 x 左右两边是否为 y，如果 是 那么 答案 - 1。
• 如果 暴力合并，时间复杂度为 O(n ^ 2)，因此可用 启发式合并 进行 优化成 O(nlogn)

进行 颜色变化 时，我们是 将 x 变成 y，且看成 将 x 和 y 合并，合并时 有可能将 x 变成 y，是符合题意的，也有可能 将 y 变成 x，这样一来，x 和 y 两种颜色映射关系会发生变化，因此我们需要分析一下 如何存储：

• 开一个数组 来存储所有颜色，用 编号 表示 某种颜色，一开始 每种颜色对应编号即为自己，对于 每种编号，由于我们需要方便的 将两个集合合并，我们可以用 单链表 存所有集合，每种颜色编号我们 下拉一个单链表，用于存储 所有这种颜色的布丁所在位置，每次根据题目要求 将 x 合并至 y 时，假如 x 所在集合大小比 y 所在集合大小更大，我们实际操作时应该 将 y 集合合并至 x 集合中，所以还应该将 映射关系颠倒一下。

代码：

#include <bits/stdc++.h>

using namespace std;
//#define map unordered_map
//#define int long long
const int N = 1e5 + 1, M = 1e6 + 10;    //节点个数 颜色个数
int n, m;
int h[M], e[N], ne[N], idx; //h[M] 每种颜色头结点 这些数组存所有节点
int col[N], sz[M], p[M];    //每个节点颜色 每种颜色集合大小 映射：每种颜色对应哪个编号
int ans = 0;

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
    sz[a] ++;
}

void merge(int& x, int& y)
{
    if (x == y) return;
    if (sz[x] > sz[y]) swap(x, y);
    for (int i = h[x]; ~i; i = ne[i])
    {
        int j = e[i];
        ans -= (col[j - 1] == y) + (col[j + 1] == y);
    }

    for (int i = h[x]; ~i; i = ne[i])
    {
        int j = e[i];
        col[j] = y;
        if (ne[i] == -1)
        {
            ne[i] = h[y], h[y] = h[x];  //将x下拉链表头插入y的下拉链边中，启发合并集合
            break;
        }
    }
    h[x] = -1, sz[y] += sz[x], sz[x] = 0;   //记得将x集合清空，y大小增加
}

signed main()
{
    cin >> n >> m;
    memset(h, -1, sizeof h);
    for (int i = 1; i <= n; ++i)
    {
        scanf("%d", &col[i]);
        if (col[i] != col[i - 1]) ++ans;
        add(col[i], i);
    }

    for (int i = 0; i < M; ++i) p[i] = i;
    while (m--)
    {
        int op; scanf("%d", &op);
        if (op == 1)
        {
            int x, y; scanf("%d%d", &x, &y);
            merge(p[x], p[y]);
        }
        else
        {
            printf("%d\n", ans);
        }
    }


    return 0;
}
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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69

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

前置知识：一般式启发式合并，树链剖分

用处：一般用来解决一类 不带修改的子树查询问题

核心思想：利用 重链剖分的性质 优化子树贡献的计算。

• 暴力：想到 O(n ^ 2) 做法。遍历 n 个节点，对 n 个节点的子树进行统计。
  细节：每次对子树统计后的信息都会删除，也就是对于这棵树会 被父亲统计多次。
• 高效：对于某个节点，我们每次 先遍历其轻儿子，每次遍历完 轻儿子 将信息 清空，最后遍历重儿子，但是 不清空重儿子的信息，将其 作为遍历剩余部分的依据，从而完成对于 每个节点信息的统计，能够证明，这样做可以 将时间复杂度从 O(n ^ 2) 优化为 O(nlogn)
• 重复利用：对于 u 节点，其 重子树 son[u]。

相关题目：abc202_e Gym 102391J CF570D CF1009F CF208E CF600E CF741D UOJ284

例题：AcWing 3189. Lomsat gelral

视频讲解

题意：

树的节点有颜色，一种颜色占领了一个子树，当且仅当没有其他颜色在这个子树中出现得比它多。求占领每个子树的所有颜色之和

思路：

先 dfs_son 求一下 每个节点的重儿子，

sz 数组 – 记录 每棵子树大小

son 数组 – 记录 每个节点的重儿子

int dfs_son(int u, int father)
{
	sz[u] = 1;
	for (int i = h[u]; ~i; i = ne[i])
	{
		int j = e[i];
		if (j == father) continue;
		sz[u] += dfs_son(j, u);
		if (sz[j] > sz[son[u]]) son[u] = j;
	}
	return sz[u];
}
1
2
3
4
5
6
7
8
9
10
11
12

之后 dfs 递归遍历每个节点遍历 的时候 优先遍历轻儿子，最后遍历重儿子，重儿子信息不清空，轻儿子信息清空，（核心de板子）

sum数组 – 对于 当前子树 而言，其 主要颜色编号之和

mx – 对于 当前子树 而言，其 主要颜色出现最多次数

void dfs(int u, int father, int op)
{
	//*第一步：搞轻儿子及其子树算其答案删贡献
	for (int i = h[u]; ~i; i = ne[i])
	{
		int j = e[i];
		if (j == father || j == son[u]) continue;
		dfs(j, u, 0);
	}

	//*第二步：搞重儿子及其子树算其答案不删贡献
	if (son[u]) dfs(son[u], u, 1);

	//*第三步：暴力统计u及其所有轻儿子的贡献合并到刚算出的重儿子信息里
	update(u, father, 1, son[u]);
	ans[u] = sum;

	//第四步：*把需要删除贡献的删一删
/*
如果当前是轻儿子，则清空：update(u, father, -1, 0); 
由于整棵子树都要清空，且当前子树重儿子也要清空，op 得传入一个不存在的编号，
0 即可
*/
	if (!op) update(u, father, -1, 0), mx = sum = 0;//这是因为update函数中会改变这两个变量值
}
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

对于上面函数，我们发现每次遍历的时候需要再写一个 函数 update，用于 递归求解整棵子树每个颜色出现次数。

void update(int u, int father, int sign, int pson)
{
	int c = col[u];
	cnt[c] += sign;	//sign 标记为正为负 可以控制是增加贡献还是删除贡献
	if (mx < cnt[c]) sum = c, mx = cnt[c];	//找最大值
	else if (mx == cnt[c]) sum += c;	//因为如果两个颜色数量相同那都得算
	for (int i = h[u]; ~i; i = ne[i])	//排除被标记的重儿子 pson 统计其它儿子子树信息
	{
		int j = e[i];
		if (j == father || j == pson) continue;
		update(j, u, sign, pson);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13

代码：

#include

using namespace std;

#define int long long
const int N = 1e5 + 10, M = N << 1;
int n;
int h[N], e[M], ne[M], idx;
int col[N], cnt[N], sz[N], son[N];
int ans[N], sum;
int mx;

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

int dfs_son(int u, int father)
{
    sz[u] = 1;
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (j == father) continue;
        sz[u] += dfs_son(j, u);/////////
        if (sz[j] > sz[son[u]]) son[u] = j;
    }
    return sz[u];
}

void update(int u, int father, int sign, int pson)
{
    int c = col[u];
    cnt[c] += sign;
    if (mx < cnt[c]) sum = c, mx = cnt[c];
    else if (mx == cnt[c]) sum += c;
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (j == father || j == pson) continue;
        update(j, u, sign, pson);
    }
}

void dfs(int u, int father, int op)
{
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (j == father || j == son[u]) continue;
        dfs(j, u, 0);
    }
    if (son[u]) dfs(son[u], u, 1);
    update(u, father, 1, son[u]);
    ans[u] = sum;
    if (!op) update(u, father, -1, 0), mx = sum = 0;
}

signed main()
{
    cin >> n;
    memset(h, -1, sizeof h);
    for (int i = 1; i <= n; ++i) scanf("%lld", &col[i]);
    int m = n - 1;
    while (m--)
    {
        int x, y; scanf("%lld%lld", &x, &y);
        add(x, y), add(y, x);
    }
    dfs_son(1, -1);
    dfs(1, -1, 1);
    for (int i = 1; i <= n; ++i) printf("%lld ", ans[i]);

    return 0;
}
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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75