# 类生成树：Kruskal 重构树与 XOR-MST ## 本节目标 学完后，你应能把并查集合并历史显式建成 Kruskal 重构树，用 LCA 回答“两点何时连通”，并利用 XOR 权值的最高不同位递归削减完全图。 ## 前置知识与课前自测 前置：Kruskal、并查集、LCA、二进制 Trie、分治。 1. 按边权递增加入边时，两点第一次连通的阈值与 MST 路径有什么关系？ 2. 两个数最高不同位为 $b$ 时，它们 XOR 的第 $b$ 位是多少？低位最多能否抵消它？ 3. 完全图 XOR-MST 中，相同数对应的多个顶点是否影响总权？
自测答案 1. 等于某棵 MST 上两点路径的最大边权，也是 Kruskal 合并它们所在分量的时刻。 2. 第 $b$ 位为 1，低位之和小于 $2^b$，不能抵消。 3. 相同数之间边权为 0，可先用零权边连成一块，去重不改变答案。
## 问题动机与核心知识 Kruskal 普通实现只保留最终 DSU，丢掉“什么时候合并”。重构树在每次成功合并两个分量时新建父节点，节点权为当前边权/时间，两个旧根作为孩子。原点是叶子，内部点权沿根方向不降。 两个原点的 LCA 正是首次把它们并入同一分量的合并节点。因此： $$ \operatorname{value}(\operatorname{LCA}(u,v)) =\min\{k:\ u,v\text{ 在前 }k\text{ 条边中连通}\}. $$ XOR-MST 则使用最高位分层。若一组数在位 $b$ 同时含 0/1，任意连接两组的边都至少花 $2^b$；生成树必须至少选一条跨边，而组内可独立递归。只需求两组间最小 XOR，而不是显式生成所有跨边。 ## 实现指南 - 重构树最多有 $2n-1$ 个节点，数组按 `2*n` 开。 - 合并新节点后，要让两个旧 DSU 根的父亲指向新节点；新节点自身是新根。 - XOR 分治前排序去重；每层范围共享更高位前缀，当前位的 0/1 在排序中连续。 - Trie 查询只需处理当前位以下，跨组的当前位代价固定为 $2^b$。 ## 精选例题 1：Qpwoeirut and Vertices ### 来源信息与题意 - VJudge：[CodeForces-1706E Qpwoeirut and Vertices](https://vjudge.net/problem/CodeForces-1706E) - 原题：[Codeforces Round 809 (Div. 2)](https://codeforces.com/problemset/problem/1706/E) - 难度：2300；考点：按时间重构树、相邻点连通阈值、区间最大值 多组连通简单无向图，边按输入编号 $1..m$。每个询问 $[l,r]$ 求最小 $k$，使编号在该区间内的所有顶点使用前 $k$ 条边两两连通。总 $n\le10^5$，总 $m,q\le2\times10^5$。
Hint 1按边编号做 Kruskal 式合并，新节点权值为边编号。
Hint 2两点 $u,v$ 的最早连通编号是重构树 LCA 权值。
Hint 3区间所有点连通，当且仅当每对相邻编号点 $(i,i+1)$ 都连通。
Hint 4预处理 `need[i]=value(LCA(i,i+1))`，答案是 `need[l..r-1]` 最大值。
### Observations、Editorial 与证明 边按编号递增处理，每次连接两个不同分量就新建合并节点。对阈值 $k$，区间相邻点全部连通则由传递性整个区间连通；整个区间连通也必然包含每对相邻点。因此最小共同阈值是相邻阈值最大值。 建树与 LCA 预处理 $O((n+m)\alpha(n)+n\log n)$，区间最大值用迭代线段树，每问 $O(\log n)$。 ### 核心伪代码与参考实现附件 ```text process input edges by index; every successful DSU merge creates a new parent node new node value = current edge index; its children are the two old component roots preprocess LCA on the reconstruction tree need[i] = value(LCA(original_vertex_i, original_vertex_i+1)) answer(l,r) = max(need[l .. r-1]), or 0 when l == r ``` 完整 GNU C++17 参考实现见附件：[CodeForces-1706E.cpp](../../参考实现/06-最小与最大生成树/CodeForces-1706E.cpp) ### 复盘与变式 若询问顶点集合不是编号连续区间，相邻编号链不再覆盖集合；可按 DFS 序、虚树或直接取集合在重构树上的最小公共祖先，取决于查询形式。 ## 精选例题 2：Xor-MST ### 来源信息与题意 - VJudge：[CodeForces-888G Xor-MST](https://vjudge.net/problem/CodeForces-888G) - 原题：[Educational Codeforces Round 32](https://codeforces.com/problemset/problem/888/G) - 大致难度：2300 左右；考点：XOR 最高位分治、二进制 Trie、隐式完全图 完全图有 $n\le2\times10^5$ 个点，点 $i$ 带值 $a_i<2^{30}$，边权为 $a_i\oplus a_j$。求 MST 权值。
Hint 1相同值先用零权边连接，可去重。
Hint 2按最高位 $b$ 把当前组分成 0/1 两组；组内 MST 独立递归。
Hint 3若两组都非空，生成树必须且只需再选一条最便宜跨边。
Hint 4把较小一组的低位插入 Trie，查询另一组的最小低位 XOR；跨边还固定贡献 $2^b$。
### Observations、Editorial 与证明 当前范围内所有数共享更高位。按位 $b$ 分开后，任意跨边权均大于任一只由更低位构成的数；MST 可先在两侧各自连通，再用一条最小跨边连接。多用跨边会形成环，删除其中一条不更差。 递归处理两侧，跨边低位最小 XOR 用 Trie 求。排序与 30 层分治，当前实现复杂度 $O(n\log^2 A)$、空间 $O(n\log A)$ 的峰值；$\log A\le30$。 ### 核心伪代码与参考实现附件 ```text sort and deduplicate values solve(group, bit): split group by current bit answer = solve(zero_side, bit-1) + solve(one_side, bit-1) if both sides exist: build a lower-bit binary trie for the smaller side answer += 2^bit + minimum lower-bit XOR across the split return answer ``` 完整 GNU C++17 参考实现见附件：[CodeForces-888G.cpp](../../参考实现/06-最小与最大生成树/CodeForces-888G.cpp) ### 复盘与变式 本题不是“所有完全图都能 Trie”。可分治是因为最高不同位严格支配全部低位；若边权改成按位 AND 或普通差值，递归结构和跨边性质都要重证。 ## 灵活性训练：Envy [CodeForces-891C Envy](https://vjudge.net/problem/CodeForces-891C) 要判断每个询问给定的边集能否同时出现在某棵 MST。提示方向：按权值处理询问边，在全局 DSU 只合并更轻边；同一询问、同一权组用临时可回滚 DSU 检查是否成环。它把本章“同权批次不能提前合并”的原则提升到离线多询问，不作为后续硬前置。 ## 扩展与联系 - Kruskal 重构树也可按边权建，用于路径瓶颈、阈值连通与离线询问。 - 最大生成树重构树的节点权沿根方向不升，比较方向相反。 - XOR 最小对、Borůvka 与 Trie 也能求 XOR-MST；选择方案时比较证明和复杂度，而非模板长度。 ## 总结与自检 1. 重构树内部节点表示什么事件？ 2. 两叶 LCA 权为何是首次连通阈值？ 3. 区间全部点连通为何只需相邻编号对？ 4. XOR 分治为何只需一条最小跨边？ 5. 去重为何不改变 XOR-MST 权值？ ## 课后训练建议 先用逐步 DSU 暴力核对重构树 LCA 阈值，再完成区间 RMQ。XOR-MST 先对 8 个数枚举完全图 MST，对照递归拆分；卡住时只展开“最高位下界”，不要直接背 Trie 代码。最后阅读 `Envy` 的同权离线框架并写出临时 DSU 必须回滚的原因。