引入
假设我们有若干个集合，大小之和为 nnn。我们需要执行 qqq 次操作，每次都是要合并其中两个集合，默认 n,qn,qn,q 同阶。
暴力做法是显然的：枚举其中一个集合的所有元素，把它加入到另一个集合。
这样做复杂度显然是 O(n2)O(n^2)O(n2) 的。
启发式合并
启发式合并的思路是比较简单的：在暴力做法的基础上，把小集合 SSS 合并入大集合 TTT 中。
这样做的复杂度看上去和暴力没什么区别，但是其实是 O(nlogn)O(n \log n)O(nlogn) 的。证明如下：
> 考虑一个元素 xxx 被枚举到的次数。假定 x∈Sx \in Sx∈S，把 SSS 并入 TTT 之后，新的集合 T0T_0T0 大小肯定至少是 SSS 的两倍，那么，如果我想让 xxx 下一次继续并入大集合 T1T_1T1 的时候，T1T_1T1 肯定要满足：∣T1∣≥∣T0∣≥2∣S∣\lvert T_1\rvert \geq \lvert T_0\rvert \geq 2\lvert S\rvert∣T1 ∣≥∣T0 ∣≥2∣S∣。以此类推。也就是说，∣Tm∣≥2n∣S∣\lvert T_m\rvert \geq 2^n\lvert S\rvert∣Tm ∣≥2n∣S∣。所以
> m≤log2nm \leq \log_2 nm≤log2 n，说明 xxx 被枚举的次数是 O(nlogn)O(n\log n)O(nlogn) 的，总复杂度是 O(nlogn)O(n \log n)O(nlogn)。
例题1
P3402 【模板】可持久化并查集
> 维护并查集，支持回退到第 kkk 次操作。
可持久化就不说了，相信大家都会。
本题的并查集不能用路径压缩，因为路径压缩的复杂度是均摊 log\loglog 的，也就是总复杂度是 O(nlogn)O(n \log n)O(nlogn)，但不保证每次复杂度是 O(logn)O(\log n)O(logn)。所以如果查询一直回退到某一次复杂度比较大的操作，路径压缩就会炸。
所以，我们考虑启发式合并。考虑在合并并查集的时候，把小的合并到大的上面就可以了。
顺便提一嘴，并查集中的启发式合并又叫做按秩合并。
代码：
例题2
P3201 [HNOI2009] 梦幻布丁
> 给定长度为 nnn 的颜色序列，mmm 次操作。
>
> 操作一：把颜色 xxx 都变成 yyy。
>
> 操作二：查询有多少颜色段。
我们可以预先求出答案，在每次合并的时候更新答案。
考虑使用 set[N] 表示每一种颜色的位置。合并的时候把小 set 合并进大 set 。对于小 set 中的位置 ppp，如果 ap−1=ya_{p-1}=yap−1 =y，则这两段颜色会合并为一段，答案减去 111；如果 ap+1=ya_{p+1}=yap+1 =y，也要减去 111。
不过有一个问题，启发式合并的交换可能会把 yyy 变成 xxx，所以我们定义 cic_ici 表示颜色 iii 的真实颜色，然后把启发式合并的交换改成 cxc_xcx 与 cyc_ycy 的交换。
代码：
树上启发式合并
树上启发式合并的思路是，对于节点 uuu，先计算它的轻儿子 vvv 自己的答案，计算完立刻清空计算用的数组，再计算重儿子 hhh 的答案，不清空，然后加上 uuu 节点的贡献，最后再次遍历轻儿子 vvv，把每一个节点的贡献加进来，最终计算出 uuu 的答案。当然，如果 uuu 是 uuu 的父亲的轻儿子，还要把自己清空。
假如计算一个节点的贡献是 O(1)O(1)O(1)，那么总时间复杂度是 O(nlogn)O(n \log n)O(nlogn)，证明如下：
> 考虑每一个轻儿子 vvv 会被遍历多少次。vvv 被遍历一次，对应着一条从 111 到 vvv 路径上的轻边，所以遍历次数为 111 到 vvv 路径上有多少条轻边。
>
> 假设 u→vu \rightarrow vu→v 是轻边，那么 size(v)≤size(u)2size(v) \leq \frac{size(u)}{2}size(v)≤2size(u) 。
>
> > 如果 size(v)>size(u)2size(v)>\frac{size(u)}{2}size(v)>2size(u) ，那么 u→vu\rightarrow vu→v 就是重边，矛盾。
>
> 所以，每经过一条轻边，子树大小至少缩小一半。因此，从 111 到 vvv 的轻边数量不超过 log2n\log_2 nlog2 n。
>
> 所以，总时间复杂度是 O(nlogn)O(n \log n)O(nlogn)。
通过证明可以知道，树上启发式合并基本跑不满。
例题1
CF600E Lomsat gelral
> 给定根为 111 的有根树，每个点有颜色，对于所有节点，求出其子树内众数的颜色编号之和。
考虑加入一个新节点 vvv 对 uuu 子树的答案的贡献。定义 cnticnt_icnti 表示颜色 iii 的出现次数，maxxmaxxmaxx 表示出现次数的最大值，sumsumsum 表示众数的颜色编号之和。
加入 vvv 后，设 ccc 表示 vvv 的颜色，如果 cntc>maxxcnt_c>maxxcntc >maxx，那么更新 maxxmaxxmaxx，重置 sum=csum=csum=c；如果 cntc=maxxcnt_c=maxxcntc =maxx，那么累加 sum:=sum+csum := sum+csum:=sum+c。
代码：
例题2
CF741D Arpa’s letter-marked tree and Mehrdad’s Dokhtar-kosh paths
> 给定一颗根为 111 的有根树，每条边有一个小写字母（从 aaa 到 vvv）。
>
> 如果一条简单路径经过的所有边的字母可以排列出回文串，那么它就是特殊路径。
>
> 对于所有节点 uuu，询问 uuu 的子树中，最长的特殊路径长度。
我们考虑什么样的路径是特殊的。显然，经过的字母数量最多只能有一个是奇数。因此，我们只关心字母出现次数的奇偶性。
由于字母只有 222222 种，考虑状态压缩进一个整数里。did_idi 表示从 111 到 iii 路径上所有字母的状压后的值。如果 popcount(du⊕dv)≤1\operatorname{popcount}(d_u \oplus d_v) \leq 1popcount(du ⊕dv )≤1，那么 u→vu \rightarrow vu→v 的路径就是特殊的。
定义 depudep_udepu 表示 uuu 的深度，maxdimaxd_imaxdi 表示 dv=id_v=idv =i 中 depvdep_{v}depv 的最大值，ansuans_uansu 表示 uuu 点的答案。对于 uuu 的轻儿子 vvv，我们遍历 vvv 的子树中的点 v′v'v′，令 D=dv′D=d_{v'}D=dv′ ，更新 ansu=max(maxdD+depv′−2depu,maxdD⊕2i+depv′−2depu,ansv)ans_u=\max(maxd_{D}+dep_{v'}-2dep_u,maxd_{D \oplus
2^i}+dep_{v'}-2dep_u,ans_v)ansu =max(maxdD +depv′ −2depu ,maxdD⊕2i +depv′ −2depu ,ansv )。
更新之后，再将 vvv 的子树所有节点的贡献加进去。
为什么这样是对的？因为在更新的过程中，还没有加入过 vvv 的子树的节点，所以更新时，不会遇到 v′→u→v′v' \rightarrow u \rightarrow v'v′→u→v′ 这种非法路径。
小细节，maxdmaxdmaxd 清空的时候要设为负无穷，而不是 000。
时间复杂度：O(nVlogn)O(nV \log n)O(nVlogn)，本题 V=22V=22V=22。
代码：
例题3
P5290 [十二省联考 2019] 春节十二响
> 给定一颗的有根树，有点权，将其划分为若干个点集合，要求每个集合内的点不存在祖先关系，最小化所有集合内最大值之和。
先考虑特殊性质，如果树是一条链，那么 111 号点将链划分为两段，我们肯定是让第一段的最大值和第二段最大值在一起，第一段次大值和第二段次大值在一起……也就是对于两段分别开一个大根堆，每次取堆顶划成一个集合。
这提示我们，设 heapuheap_uheapu 表示 uuu 子树内，我们划分出的每一个集合的最大值所构成的大根堆。对于 uuu 的儿子 vvv，我们把 heapvheap_vheapv 与 heapuheap_uheapu 合并，最后再单独把 MuM_uMu 单独扔到堆里。
此时使用启发式合并就是 O(nlogn)O(n \log n)O(nlogn) 的。为什么不是 O(nlog2n)O(n \log^2 n)O(nlog2n) 呢？因为本题的 heapvheap_vheapv 并没有真正并入 heapuheap_uheapu ，只是取了一个 max\maxmax，所以每个点只会被合并 111 次，而不是 log2n\log_2 nlog2 n 次。
注意，本题与P3201 [HNOI2009] 梦幻布丁类似，由于有启发式合并的交换操作，所以要记录每个节点真正的编号。
代码：
例题4
CF1709E XOR Tree
> 给定一棵树，带点权，你可以进行若干次如下操作：把一个点的点权改成一个任意正整数。求最少次操作，使得不存在异或和为 000 的简单路径。
由于我们修改点权是任意数，所以可以当作是把这个点以及连的边都删掉。
设 dud_udu 表示从 111 到 uuu 的异或和，显然 u→vu \rightarrow vu→v 的异或和是 du⊕dv⊕aLCA(u,v)d_u \oplus d_v \oplus a_{\operatorname{LCA}(u,v)}du ⊕dv ⊕aLCA(u,v) 。
考虑自底向上贪心。枚举 xxx，判断是否存在 u,vu,vu,v 使得 LCA(u,v)=x\operatorname{LCA}(u,v)=xLCA(u,v)=x 并且 du⊕dv=axd_u \oplus d_v=a_xdu ⊕dv =ax ，如果有，那就删除 xxx。
设 SxS_xSx 表示 xxx 子树内未被删除的节点的 *** 值。先把 dxd_xdx 加入 SxS_xSx ，接着我们枚举 xxx 的子树 uuu，遍历 i∈Sui \in S_ui∈Su ，判断 i⊕axi \oplus a_xi⊕ax 是否属于 SxS_xSx 。如果是，说明 xxx 需要删除，清空 SxS_xSx 并不再枚举。如果最后不需要删除，就把 SuS_uSu 合并到 SxS_xSx 中。这个过程使用启发式合并，可以做到 O(nlog2n)O(n \log^2 n)O(nlog2n)。
代码：
