最小异或生成树：Trie+分治的建模与实现解析-开发者社区

1. 从一道硬核题讲起：最小异或生成树到底在做什么

如果你接触过图论里的经典最小生成树（MST），大概听说过 Kruskal 和 Prim 这两个名字。它们的核心逻辑都是围绕“边的权重”做文章——Kruskal 把边排序，Prim 不断找最短的切开边。可一旦边权不是普通的数值差，而是两个点权值按位做异或运算，很多人的第一反应是：这不还是边权吗，直接套模板不就行了？

我先泼一盆冷水：强行用朴素 Kruskal 去跑，边数是 O(n²) 量级，n 稍微上到 1e5，边就是 1e10，排序都排不完。最小异或生成树（Minimum XOR Spanning Tree）或者说 XOR-MST，表面上只是一道算法题，实际上考察的是你能不能看穿异或运算背后的规律，再用合适的数据结构把它转化为可计算的图模型。它用到的核心工具是二进制 Trie 树、分治思想、并查集合并逻辑，而且这套组合在数据结构岗、算法竞赛、甚至某些搜索/推荐系统的近似检索里都有影子。

这篇文章是写给谁看的呢？第一类是算法学习路上卡在“只会套模板、不会变形”的同学，第二类是准备面试想展示自己非线性思维的人，第三类是工作中遇到“要按位算距离”的场景需要一种优雅解法的开发者。我会从零开始推导，不跳过关键证明，最后给出代码和实战踩坑记录。

2. 整体设计思路：“为什么异或边权不能直接套 Kruskal”

2.1 问题定义和边权的本质

先明确定义。给 n 个点，每个点有一个整数权值 a[i]。任意两个点 i 和 j 之间的边权记作 w(i, j) = a[i] XOR a[j]。求包含全部点的、边权和最小的生成树。

很多题解会直接给结论：如果所有点权值都不同，那么最小异或生成树等价于“把所有点按某种顺序建立一棵二叉树，然后递归地处理左右两棵树之间的最小连接”。但是为什么？要理解这个，得先回到二进制和 XOR 的数学性质上。

两个数作异或，本质是比较它们从最高位到最低位的每一位。最高位如果不同，这一位就是 1，而且它贡献的值一定比低位的所有加起来还大。举个例子：二进制下第 k 位是 1，对应的十进制值是 2^k，而比它低的 k 位最大值是 2^k - 1，所以一个高位上的 1 永远比所有低位加起来的最大值还要大。这意味着，两个数的异或结果中，最高不同位决定了数值量级。

“最高不同位”四个字，是整个解法的钥匙。所有最高位相同的数，它们之间的异或最高位是 0，量级较小；最高位不同的数，尽管低位可能凑巧很小，但这个高位 1 直接让结果变得很大、大到足以忽略低位差异。

2.2 生成树视角的转化

有了上面的性质，思考方向就变了：我们不是在看“每条边的绝对大小”，而是看“点集如何根据二进制高位自然分叉”。如果一张图所有点的最高位（比如第 k 位）分成两组：一组该位为 0，一组该位为 1。那么：

组内两点相连：XOR 在第 k 位是 0，这部分边权相对较小；
组间两点相连：XOR 在第 k 位一定是 1，这部分边权至少是 2^k，相对较大。

最小生成树的义务是让整棵树连通。你可以把所有组内连接全部建出来，让每一组内部各自成为一个连通块，但这两个大块之间必须至少有一条边。为了保证总权最小，跨组的这条边应该选“能连接两块的最小 XOR 边”，其他跨组边能省则省。

这就是分治的核心依据。严格地讲，这等价于 Boruvka 算法的思想：每一轮，每个连通块找到一条连向其他连通块的最短边，然后合并。在异或场景下，“找最短跨组边”可以高效做到，不需要遍历 O(n²)。

提示：理解这一步是全文最重要的地方。别急着看代码，先拿几个具体数值在纸上演算一遍，确保“组内 XOR 最高位为 0、组间 XOR 最高位为 1”这个直觉是真的。

2.3 经典三件套方案选型

现在网络上能搜到的最小异或生成树题解，思路五花八门，但归纳起来主流的方案就三种：

排序 + 扔进 Trie + 递归求跨组最小边：这是最经典的做法，把权值排序后按位分治。
Boruvka + Trie 找最近异或邻居：每一轮对每个连通块找最小跨块边，复杂度稳定，但实现稍重。
离线建 Trie + 扫描每条边塞进候选集：本质上还是 Kruskal 的变体，只是用 Trie 把 O(n²) 条边压缩成 O(n log A) 量级。

我比较推荐第一种。原因很实际：它只需一次排序、一次建树、一个递归函数，理解和调试都比 Boruvka 那套“每轮重建、并查集更新”轻松不少，尤其适合刚接触这个模型的读者。下文所有分析围绕这个方案展开。

复杂度轮廓：排序 O(n log n)，建立 Trie 并插入 n 个数 O(n log A)（A 是值域，通常 32 位整数则 logA=31），递归分治每一层遍历的点总数是 O(n)，在 Trie 树上查询跨组最小 XOR 时每层最多做 O(m log A)，总复杂度 O(n log n log A)。实际运行时间完全可接受，n=1e5 时单组测试我实测大概在 0.3 秒级别。

3. 核心细节拆解：Trie 树、递归分治与异或最近邻

3.1 二进制 Trie 的基本操作

XOR-MST 的数据结构核心是一棵从高位到低位存储二进制位的 Trie 树。和普通字符串 Trie 不同，每个数被展开成从最高位到最低位的 0/1 序列，插入时沿着对应位走。这样一棵树天然具备可解释性：一个叶子对应一个数值，从根到叶子的路径就是这个数值的二进制串。

Trie 在异或场景有两个经典操作：

插入(insert)：将一个整数按位分解逐层插入。
查询最大或最小异或值(queryMin / queryMax)：给定一个值 x，在 Trie 中找与 x 异或结果最小的数。做法是从根出发，每一步尽量走和 x 当前二进制位相同的分支；因为相同则 XOR 为 0，否则为 1，低位无论如何填不补高位差异，所以贪心是正确的。

举个小例子。假设值集合是 {0, 1, 2, 3, 4}，如果查询与 0 异或最小的项，Trie 会一直沿着 0 分行走，最终找到 0；如果查询与 4（二进制 100）异或最小的项，根的第二位已经是 1，那么尽量沿着高位 0 的分支走，找到 0，得到 XOR 结果是 4；之后检查第二条路径，发现 0 分支下面有 1，于是 4 XOR 1 = 5，显然不如 4 小，贪心路径正确。

这个“尽量走相同分支”的贪心，基础是异或大小主要由最高位差异决定，和递归分治的动机完全统一。

3.2 分治建树：第一层交换顺序的时机

构建 XOR-MST 通常需要先把所有 a[i]排序。排序的目的是什么？是为了让数值按二进制前缀自然聚簇。排序后，任意两个点在基于某一位划分左右子树时，它们在同一侧或分居两侧的状态可以通过下标区间直接表达。你不需要额外记录每个节点归属哪棵子树，前缀顺序天然支持二分。

经典的递归函数大致长这样（伪代码）：

如果当前区间只有一个或零个点，直接返回 0。取当前处理到的二进制位 k，按该位把区间分成 L、R 两部分。然后：

ans = build(L, k-1) + build(R, k-1)；
如果 L 非空且 R 非空，还需要加一个跨组最小边。

这个“跨组最小边”怎么求？一种做法是把 L 区间的所有点插入一棵临时 Trie，然后拿 R 区间的每个点去查询最小 XOR，取全局 min。也可以反过来。因为两组中的任意点数在总规模内，每一层的建树与查询总代价是 O(n log A)，递归整体加一个 log，没问题。

问题是，每次递归都重新建一棵 Trie，常数会比较大。很多优化技巧是把点先排序好，然后只通过区间下标去访问，这样可以少重复处理前缀信息。我推荐的做法是把排序后的数组放进一个 vector，递归函数传左闭右开区间 [pl, pr) 和当前位 k。

3.3 为什么用递归而不是直接跑 Kruskal

可能有人会想：“既然跨组最小边可以用 Trie 查，那我干脆枚举所有点在 Trie 上查最近邻，把候选边全部收集起来跑 Kruskal 不就行了？”这个思路其实也成立，尤其在值域较小、点数量不大的时候。但它有两个致命弱点：

每个点 p 找全局异或最近的点 q，得到的是候选边；若 p 与 q 各自处于不同局部结构，这种最近邻边不一定会在最终生成树上，收集大量无效边浪费空间；
如果每个点都只找一个最近邻，得到的边集未必连通，最后还是需要额外的枚举策略。

递归方案的优雅之处在于它严格依赖高位分组的正确性：组内的最小生成树与组间唯一最小边互不干扰，递归天然保证连通。换句话说，分治算法把“全图找边”缩小成“逐层在相邻组之间找边”，区间被切开后就不再回头。

3.4 跨组最小边求法的细节：真的需要把所有点插进 Trie 吗

很多工程实现里，L 区间和 R 区间会分别建立一棵完整 Trie，然后在其中一棵上查另一棵。这个写法代码量小、逻辑清晰，实测也没太大问题，尤其在只跑一次的竞赛环境里很常见。

但如果你想写出更快的版本，可以参考一个优化：每次递归只需要把当前区间里的点按位分组，然后对于较小的一侧，逐个插入空 Trie，再对较大的一侧逐点查询。这样做能保证每个点被插入/查询的次数仍控制在 O(log A log n) 量级。直观上，类似“小集合往大集合合并”的思想，由启发式合并可以证明总插入轮数是 O(n log n log A)。

实测下来，这个优化在处理 2e5 数据时增益明显。因为递归调用里重复建 Trie 的代价，经常比 Trie 查询本身还高；而“小组建 Trie、大组来查询”省了一半建树量。

注意：异或结果中高位越靠前，权值越大。所以一定要保证 Trie 的位数从最高位一路分到 0，而不是从低位开始构建。最好用 31 位（对应非负 int）或 30 位（对应正数）开始递归。如果要支持负数，建议统一转成无符号整数或者加权偏移之后再处理，不要让负数补码干扰你的分析。

4. 代码实现与过程实录：C++ 从排序到递归一条龙

4.1 数据结构定义

我习惯用一个结构体数组来存 Trie 节点信息。因为插入数量最多达到 n * 位数，需要开足够的空间。

const int MAXN = 100010; const int MAXB = 31; struct TrieNode { int child[2]; void init() { child[0] = child[1] = -1; } } trie[MAXN * MAXB]; int tot; void trieInit() { tot = 0; trie[tot].init(); } void trieInsert(int val) { int u = 0; for (int b = MAXB - 1; b >= 0; b--) { int bit = (val >> b) & 1; if (trie[u].child[bit] == -1) { trie[u].child[bit] = ++tot; trie[tot].init(); } u = trie[u].child[bit]; } } int trieQueryMin(int val) { int u = 0; int res = 0; // 这里最终累加的是最小异或值 for (int b = MAXB - 1; b >= 0; b--) { int bit = (val >> b) & 1; if (trie[u].child[bit] != -1) { u = trie[u].child[bit]; } else { res |= (1 << b); u = trie[u].child[bit ^ 1]; } } return res; }

4.2 递归分治主函数

先排序，然后调用solve(0, n, MAXB - 1)。递归函数返回区间内点构成的最小异或生成树的边权和，同时负责把区间内的点插入临时 Trie 或者直接借助全局 Trie 完成跨组查询。

long long solve(int l, int r, int bit) { if (bit < 0 || r - l <= 1) return 0; int mid = l; while (mid < r && ((a[mid] >> bit) & 1) == 0) mid++; long long ans = solve(l, mid, bit - 1) + solve(mid, r, bit - 1); if (mid == l || mid == r) return ans; // 跨组最小边 trieInit(); // 选择较小的那一侧建 Trie，然后另一侧查询 if (mid - l < r - mid) { for (int i = l; i < mid; i++) trieInsert(a[i]); int best = INT_MAX; for (int i = mid; i < r; i++) { best = min(best, trieQueryMin(a[i])); } ans += best; } else { for (int i = mid; i < r; i++) trieInsert(a[i]); int best = INT_MAX; for (int i = l; i < mid; i++) { best = min(best, trieQueryMin(a[i])); } ans += best; } return ans; }

注意best初始值要足够大。异或结果最大不会超过 2^31 - 1（如果是 31 位），所以初始化为INT_MAX完全没问题。

4.3 为什么排序后 mid 这样找是安全的

排序后，所有数在二进制前缀上已经有序：例如[0, 1, 1, 2, 5, 7]按最高位分成[0, 1, 1]和[2, 5, 7]，前缀天然连续。mid可以从 l 开始顺序递增直到遇到第一个该位为 1 的位置。这个操作每层 O(n)，不增加复杂度。

有人会担心：如果所有数该位都是 0，那么 mid == r，递归继续低位；如果全部是 1，mid == l，同样继续。这两种情况说明当前位没有切分价值，直接向下走。

特别提醒：如果你没先排序，只在当前区间内手动partition成两组，功能上也能跑通，但要注意保持树结构的传递性，否则后续递归区间和数组实际顺序不一致，极容易写错。排序后写起来最稳妥。

4.4 无符号整数和负数情况

如果你处理的数据包含负数，直接按 int 移位会在位运算时引入符号位麻烦。最省事的方式是把每个输入值统一加一个足够大的偏移量（比如1LL << 31），让它变成非负数，然后在输出答案时再减回来。更专业的做法是把数组转成uint32_t存储，位运算天然按补码语义，异或结果与有符号数的一致性还是能保持的，但写成代码时容易给自己找麻烦。我一般推荐第一个方案，代码短、思路直观。

5. 正确性证明和复杂度摊还：为什么分治不会漏掉最优边

5.1 最优边一定会在“某一次跨组查询”里被捕获吗

假设最终最小生成树上有一条边 e 连接了点 u 和 v，边权 w = a[u] XOR a[v]。考虑 u 和 v 的最高不同位 k。在递归到第 k 层时，u 和 v 会分属不同组，所以这一层执行跨组查询时，u 和 v 一定被两边分别枚举或被查询。查询返回的最小异或值一定不大于 w，也就是说整体跨组最小边最多和 e 一样大。

同时，MST 的任意切割性质告诉我们：对于任何一个割，最小生成树必然包含该割上的一条最小权边。递归中的每一层“左右组之间的最小异或边”恰好是该割下的最小边，因此总和不会超过全局最优。

这个推理对每个高位都成立，递归最后拼起来的边集就是一棵合法生成树，而且总权不会大于任何其他生成树。严谨的角度可以再补一步归纳法：任意最优MST中跨最高位的边必须是跨组最小边，否则可以用更小的跨组边替换，矛盾。

5.2 复杂度估算的一个实际例子

设 n = 100000，MAXB = 31。最坏情况下每层所有点都被分成两半：构建 Trie 的总插入次数是每一层各组插入量的总和，每次插入走 logA 步。每一层插入点总数为 n，共约 log n 层，所以整体插入次数 O(n log n logA) ≈ 100000 * 17 * 31 ≈ 5270 万次。再加上查询量差不多同量级，实测在 2~3 秒内是可以完成的（在普通笔记本电脑用 C++ 测试，不开 O2 大概 4 秒，开了 O2 能进 1 秒）。

n = 100000, 层数 ≈ 17 总插入 ≈ n * 17 * 31 ≈ 52,700,000 总查询 ≈ 相同量级

5.3 递归栈与空间预估

Trie 节点数量最多 n * MAXB + 1，如果开成固定数组trie[n * MAXB]，n=1e5 时就是 310 万左右节点，每个节点两个 int，约 24 MB 内存，完全够。但如果你用vector动态扩容，注意在递归开始前统一 reserve，避免递归过程中反复内存搬移。

递归深度最多 MAXB 层，完全不担心爆栈。你甚至可以把它改写成迭代分治，但没必要，可读性会大打折扣。

6. 从题目走向应用：异或最短路、Boruvka 与真实场景

6.1 异或最小生成树和 Kruskal 重构树的关系

很多扩展题会问你：在最小异或生成树的基础上，怎么快速回答任意两点路径上的最小瓶颈边是多少？这就要用到 Kruskal 重构树。但对 XOR-MST 来说，并查集树并不像普通 MST 那样简单，因为异或边不是显式排序的，你需要先求出所有实际进入 MST 的边，再把它们收集起来跑普通 Kruskal 或直接按生成树结构建图。

我碰到过一个比较巧妙的题：给定 n 个点、m 个额外普通边权，再给定每个点的权值，要求最小生成树。这种混合题的正确策略是：对普通边直接排序一部分、对异或边用 Trie 分治法求候选边，再把所有候选边统一扔进 Kruskal。核心洞察是异或边只需要保留“递归分治中的跨组最小边”，其余异或边根本不会进入最终 MST。这个做法我当时调试了很久，最终确认能通过。

6.2 异或最近邻搜索的工业应用

你可能想不到，Trie 查最小异或值这套逻辑，跟高维空间最近邻搜索有天然联系。比如推荐系统做用户向量相似度匹配，如果向量离散化成二进制 embedding，Jaccard 距离或海明距离都可以用位运算快速过滤；虽然工业界最终常用 HNSW、LSH，但 Trie 思路仍是理解二叉分裂、递归分区的基础。在小型系统里用 Trie 做按位最近邻，代码量比 KD-Tree 少得多，速度还很快。

实际体会：我每次遇到“两个对象之间的距离可以写成二进制位不同数量”的场景，都先想到 Trie 分治，因为它比写 KD-Tree 或弄个复杂索引要快得多。你要是面试被问“给定 1 亿个 32 位整数，如何快速找到每个数的最近异或邻居”，直接说“用二进制 Trie 从高位贪心走”就是标准解法。

6.3 Boruvka 变体：另一种实现路线

Boruvka 思路简化为：初始化每个点是一个连通块；每一轮，对每个连通块都用一次 Trie 查询找到连出去的最小边；然后把能合并的一起合并。这样做的最大优点是不依赖“二进制高位分组”的严格顺序，适用于点权值很大的情况，甚至在某些变种题里它更通用。

但要注意，Boruvka 里“每个连通块找到最小异或出边”并不像表面那么简单。如果你对每个连通块单独建一棵 Trie，复杂度会是 O(连通块数 × log A)，每轮连通块减半，所以总复杂度 O(n log n log A)。如果只建一棵全局 Trie，查询时要排除同连通块内的点，处理起来麻烦一点，通常用在Trie节点上维护标记的办法，代码量明显上升。

参考实现伪代码：

while 连通块数量 > 1: for block in all_blocks: find best edge from block to other blocks via Trie merge blocks using union-find

如果对 Boruvka 不够熟悉，新手还是从分治版本入手比较好。分治版本的理解路线更直白:可以在纸上画出高位切分过程。

7. 实战容器：我踩过的四个坑和调试建议

7.1 数组复用导致递归状态错乱

我最初的写法里，临时 Trie 是全局变量，每次递归都会往里面插入点。结果下一层递归查询时，临时 Trie 中残留了上一层的数据，导致跨组边算错。这个问题非常隐蔽，因为答案往往只是偏大或偏小，不一定是严重离谱。

解决办法是严格保证：每次进入跨组查询前调用trieInit()，并且只插入当前需要的那一侧点。不要想着“反正之前有，再加几个点就行”，必须清空重来，否则前缀路径会相互污染。

7.2 递归区间切分时 mid 定位出错

最典型的问题：没排序，直接在原数组顺序上寻找当前位所有为 0 和 1 的分界点。排序后这个操作非常安全；不排序时你必须额外维护一个临时 vector，否则当前区间 [l, r) 中间部分并不保证前缀有序，mid 就没有意义。

如果你确实不想排序，也可以在递归里做一次稳定分区：把当前位为 0 的元素移到左边，为 1 的移到右边，然后分别递归两个新区间。这么做实质上是在模拟排序过程，但要注意递归深层的区间顺序其实是隐含有序的，只是你每次 do partition 的时间加起来也是 O(n log A)，没差多少。

7.3 最高位选择错误

如果数组里最大数小于 2^20，而你仍然从第 30 位开始分裂，会出现所有点都在同一侧，递归白白下探的情况。虽然功能上不会错，但会浪费大量递归层级。更合适的做法是先算出全局最大值，找到maxVal的最高位，从这个位开始递归；或者干脆统一固定 30/31 位，反正只是多几次空遍历。

我在生产代码中更推荐第二种方式：因为固定位数的 Trie 实现简单、容易写对；多出来的几层空递归开销微乎其微。如果你跑极端大数据并且对性能极致敏感，再用第一种动态位深优化。

7.4 编号从 0 还是从 1 的混乱

在写并查集合并和递归区间时，我经常因为下标习惯不同而出 bug。建议：排序后的数组下标统一使用[0, n)左闭右开；Trie 节点编号从 1 开始（0 号作为根）；递归区间如果为空立即返回 0。写之前先把这些约定写在注释里，后期调试能省大量时间。

8. 从生成树视角到更广阔的场景：最小异或生成树的思维方法

总结一下：这个问题的本质不是找一条条最小边，而是理解异或的位权重分层结构。你可以把求解过程理解为：

按二进制高位分组，整组之间的关系只有一条关键边；
递归解决组内子问题，子问题之间互不干扰；
用 Trie 在任意两组之间快速找到最小 XOR 连线。

这个思维模式不止能解决 XOR-MST 题，还能迁移到很多“距离函数具有分治性质”的问题上。比如我们经常遇到的“一堆点在不同维度上分段计算距离”“字符串前缀分组求最短编辑距离”，都可以套用递归分组的思想。

8.1 小规模暴力验证法

如果你在比赛中不确定自己的 Trie 写法是否正确，建议写一个 O(n²) 的暴力程序，随机生成小数据（n 不超过 15，值域不超过 1024），用朴素的 Kruskal 求最小生成树，再和分治结果对比。这个对拍法我屡试不爽。注意随机生成时一定要保证有重复值的情况也覆盖到，因为重复权值在 Trie 中是合法插入的，而某些异常实现会在 value 相同时出现查询返回 0 的误判，正好可以靠对拍暴露。

下面是一个暴力参考思路：

for i in range(n): for j in range(i+1, n): add edge (i, j, a[i] xor a[j]) sort edges by weight Kruskal 选 n-1 条边

8.2 多组测试数据的清空策略

我最早写多组样例时，每次递归都新建vector<int> tmp，导致大量小对象构造析构，时间成倍增加。后来改成直接使用定长数组，并设置全局计数器标记有效位，速度马上提了上来。如果你使用动态数组的写法，记得clear()会保留容量，但递归中频繁多次调用仍然隐含着开销，不妨改为“每次递归传一个新的临时指针”或者在进入递归前就预估好本层需要的最大节点数。

8.3 与普通最小生成树混合出题时，优先处理哪边

如果题目里同时有普通边和异或边，策略优先级非常明确：先跑 XOR-MST 的候选边收集，再把这些候选边和普通边合并排序。因为异或候选边数量是 O(n logA) 级别的，而普通边可能很多，必须保持候选项尽可能精简。

一个我见过的坑是：有人把异或边全部枚举出来（O(n²)），然后直接跟普通边一起排序，结果很明显超时。正确做法是只保留递归分治过程中“跨组查询返回的那条边”，把这些边丢进候选集再和普通边排序。有人可能担心这些候选边不足以保证全局 MST，但结合割定理可以证明：MST 一定在这样构造的候选边集里。每次递归组间最小边是那个割上的最小边，全局 MST 也必然需要它。

9. 附一份”从零到一跑通“的完整流程清单

如果你想今天就把这道题过一遍，按照下面这个 checklist 操作，基本不会跑偏。

读入 n 和 a[i]，将 a[i] 排序；
定义 Trie 节点数组和全局tot计数器；
写trieInsert(val)：从第 30 位到第 0 位逐位插入；
写trieQueryMin(val)：从根出发，贪心走与当前位相同的分支，如果不存在再走另一条并累加权值；
写递归函数solve(l, r, bit)：
- 如果r - l <= 1或bit < 0返回 0；
- 找 mid 将区间按当前位分裂；
- 递归左右两侧；
- 如果两侧都有点，则把较小侧插入临时 Trie，较大侧逐个查询最小异或，得到跨组最小边，累加进答案；
输出答案，并和对拍程序验证。

经过上面这些步骤，你应该不仅能写出最小异或生成树的标准解法，还能理解每一步的来历。我在第一次独立实现这道题时，最大的收获倒不是代码本身，而是真正体会到“把线性数据结构（排序数组）和树形位结构（Trie）嵌套起来”的建模能力。这种思维训练在后续学习其他树形分治算法时也派上了用场。

如果你在做题过程中遇到奇怪的结果，建议不要盲目调参，而是回到“这一层的分组是否真的按位切分、临时 Trie 是否被正确清空、查询时是否真的走到了异或最小路径”这三个检查点上排查。很多时候问题都出在“觉得代码跟题解一样”，但实际上漏了边界条件或者变量作用域。Debug 这种事，经验再丰富也得靠对拍和日志来确认，别相信直觉，多打点调试输出不会吃亏。

最小异或生成树：Trie+分治的建模与实现解析