（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 < 1 e 5 + 1 、 0 < A i ， x ， y < 1 e 6 ） （限制条件：0 < n，m < 1e5 + 1、0 < Ai，x，y < 1e6） （限制条件：0
先想想 如何统计颜色段的数量，
初始时 进行统计的时候，可以 直接扫描一遍整个序列，每次看看 当前颜色是否和前一个一致，如 不一样，则 段数 ++，否则看下一段。
关键在于每次合并 两种颜色 的时候，如何维护段数，我们不妨 设它为 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 集合中，所以还应该将 映射关系颠倒一下。
#includeusing 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("%dn", ans); } } return 0; }
（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];
}
之后 dfs 递归遍历每个节点遍历 的时候 优先遍历轻儿子，最后遍历重儿子，重儿子信息不清空，轻儿子信息清空，（核心de板子）
sum数组 – 对于 当前子树 而言，其 主要颜色编号之和
mx – 对于 当前子树 而言，其 主要颜色出现最多次数
void dfs(int u, int father, int op)
{
/
if (!op) update(u, father, -1, 0), mx = sum = 0;//这是因为update函数中会改变这两个变量值
}
对于上面函数，我们发现每次遍历的时候需要再写一个 函数 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);
}
}
代码：
#includeusing 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; }
