# 类生成树：Kruskal 重构树与 XOR-MST

## 本节目标

学完后，你应能把并查集合并历史显式建成 Kruskal 重构树，用 LCA 回答“两点何时连通”，并利用 XOR 权值的最高不同位递归削减完全图。

## 前置知识与课前自测

前置：Kruskal、并查集、LCA、二进制 Trie、分治。

1. 按边权递增加入边时，两点第一次连通的阈值与 MST 路径有什么关系？
2. 两个数最高不同位为 $b$ 时，它们 XOR 的第 $b$ 位是多少？低位最多能否抵消它？
3. 完全图 XOR-MST 中，相同数对应的多个顶点是否影响总权？

<details><summary>自测答案</summary>

1. 等于某棵 MST 上两点路径的最大边权，也是 Kruskal 合并它们所在分量的时刻。
2. 第 $b$ 位为 1，低位之和小于 $2^b$，不能抵消。
3. 相同数之间边权为 0，可先用零权边连成一块，去重不改变答案。

</details>

## 问题动机与核心知识

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$。

<details><summary>Hint 1</summary>按边编号做 Kruskal 式合并，新节点权值为边编号。</details>
<details><summary>Hint 2</summary>两点 $u,v$ 的最早连通编号是重构树 LCA 权值。</details>
<details><summary>Hint 3</summary>区间所有点连通，当且仅当每对相邻编号点 $(i,i+1)$ 都连通。</details>
<details><summary>Hint 4</summary>预处理 `need[i]=value(LCA(i,i+1))`，答案是 `need[l..r-1]` 最大值。</details>

### 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 权值。

<details><summary>Hint 1</summary>相同值先用零权边连接，可去重。</details>
<details><summary>Hint 2</summary>按最高位 $b$ 把当前组分成 0/1 两组；组内 MST 独立递归。</details>
<details><summary>Hint 3</summary>若两组都非空，生成树必须且只需再选一条最便宜跨边。</details>
<details><summary>Hint 4</summary>把较小一组的低位插入 Trie，查询另一组的最小低位 XOR；跨边还固定贡献 $2^b$。</details>

### 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 检查是否成环。它把本章“同权批次不能提前合并”的原则提升到离线多询问，不作为后续硬前置。

## 高阶扩展：Blue and Red Tree——把操作顺序倒过来同步缩点

### 来源信息、题意与范围

- VJudge：[AtCoder-agc014_e Blue and Red Tree](https://vjudge.net/problem/AtCoder-agc014_e)
- 原题：[AtCoder Grand Contest 014 E](https://atcoder.jp/contests/agc014/tasks/agc014_e)
- 官方难度口径：1400 分；考点：逆序操作、两棵树同步缩点、启发式合并

初始蓝树与目标红树各有 $N$ 个点。一次操作在当前全蓝边路径上删一条蓝边，再连接路径两端加入红边；共做 $N-1$ 次。判断能否恰好得到目标红树。$2\le N\le10^5$。

<details><summary>Hint 1：正向模拟为什么难</summary>

加入红边后它不能再出现在“全蓝路径”上；一次选择会改变后续所有可用路径，局部贪心没有明显安全性。

</details>

<details><summary>Hint 2：倒放最后一次操作</summary>

最后只剩一条蓝边要删、最后一条红边要加。把已经处理完的点集看成连通块，这两条边必须连接同一对块。

</details>

<details><summary>Hint 3：缩点后的贪心条件</summary>

只要当前有一对连通块之间同时存在蓝边与红边，就可安全合并；重复到只剩一个块即为可行。

</details>

### Observations

1. 正向状态需记录哪些红边已加入、哪些蓝边仍在，搜索空间指数级；倒序只关心尚未展开的连通块划分。
2. 若可行，按蓝边被删除的逆序看，每一步对应的一蓝一红边连接同一对当前块；这把“路径操作”改写为“两棵树同步收缩”。
3. 可合并对不必猜顺序：收缩一对合法块只是在任何可行收缩序列中提前处理这两个不可再区分的块，不会破坏其余边的颜色存在性。

### Editorial、证明与复杂度

从单点划分开始。若两个当前块 $A,B$ 之间蓝、红边都存在，就合并它们。必要性来自倒放原操作：设正向第 $i$ 次删蓝边 $b_i$、加红边 $r_i$，在更晚的蓝边已删完后，$b_i,r_i$ 的端点落在同一对剩余蓝森林连通块中。逆序便是一串合法同步合并。

充分性也按合并序列倒放：若依次用蓝边 $b_i$、红边 $r_i$ 合并块，把顺序反转；当执行对应正向操作时，红边两端在当前蓝森林中由该次蓝边所在路径连接，删 $b_i$ 再加 $r_i$ 合法。故能合成一个块当且仅当原操作可行。

实现为每个并查集根维护 `neighbor -> color_mask`，蓝为 1、红为 2；掩码为 3 的块对进入队列。合并时把较小邻接表逐项搬到较大表，并同步改写邻块中的反向键。每条表项至多被搬 $O(\log N)$ 次，期望时间 $O(N\log N)$、空间 $O(N)$。

### 核心伪代码、边界与附件

```text
for every blue edge between components u,v: adjacency[u][v] |= BLUE
for every red edge between components u,v: adjacency[u][v] |= RED
queue every pair whose mask is BLUE|RED
while queue not empty:
    u,v = current DSU roots of the pair
    if u == v or current mask is not both colors: continue
    merge the smaller adjacency map into the larger one
    whenever a merged neighbor mask becomes both colors, enqueue that pair
answer YES iff exactly one component remains
```

同色树不可能在两个已由同色边连通的块间留下两条独立跨边，否则原树成环，因此两位掩码足以，不需记录重数。队列项会过期，弹出后必须重新 `find` 并复查掩码。完整 GNU C++17 附件：[AtCoder-agc014_e.cpp](../../参考实现/06-最小与最大生成树/AtCoder-agc014_e.cpp)

### 复盘与变式

识别信号是“两个树结构按同一连通块划分逐步收缩”。若蓝图或红图不是树，同色平行跨边可能有实际重数含义，掩码实现和充分性证明都需重做。

## 衔接题：Red and Blue Spanning Tree

### 来源与定位

- VJudge：[AtCoder-agc064_b Red and Blue Spanning Tree](https://vjudge.net/problem/AtCoder-agc064_b)
- 原题：[AtCoder Grand Contest 064 B](https://atcoder.jp/contests/agc064/tasks/agc064_b)
- 官方难度口径：600 分；$N,M\le2\times10^5$

边有红蓝色，每个点也指定一种颜色；构造一棵生成树，使每个点至少关联一条与自身指定颜色相同的树边。它作为“先满足约束森林、再补成生成树”的台阶，不占三个正式高阶名额。

<details><summary>Hint 1</summary>把边分为同时满足两端、只满足一端、两端都不满足三类。</details>
<details><summary>Hint 2</summary>第一类边尽量用并查集取成森林；被选边的两个端点都已满足。</details>
<details><summary>Hint 3</summary>第二类边从“已满足但不受益的一端”向“尚未满足且受益的一端”传播，最后任意补边连通森林。</details>

第一阶段选第一类边的极大无环子集。若一个第一类连通块含边，其中所有非孤立点都已满足。对第二类边定向：边色不匹配的端点指向匹配的端点；从已满足点 BFS，每次选边把新点纳入森林并标记满足。未能到达的点若存在，则它所在第二类结构只能靠每点各取一条边而必成环，故无解；全部满足后，原图连通保证可用剩余任意颜色边做 Kruskal 补成树。三阶段都只加跨并查集边，所以结果无环；最终有 $N-1$ 边且连通。时间 $O((N+M)\alpha(N))$。

```text
take a maximal forest of edges whose color matches both endpoints
direct every one-end-matching edge from non-beneficiary to beneficiary
BFS from already satisfied vertices and select propagation edges
if some vertex is unsatisfied: No
otherwise Kruskal-add arbitrary remaining edges until connected
```

完整 GNU C++17 附件：[AtCoder-agc064_b.cpp](../../参考实现/06-最小与最大生成树/AtCoder-agc064_b.cpp)

## 扩展与联系

- 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 必须回滚的原因。