2024年我在整理某算法练习平台的题目时，遇到过一道让我印象深刻的题，编号恰好是22。它的题干并不复杂：给一棵树，每条边上有权值，定义任意两点间的距离是路径上边权的异或和，求所有点对之间距离的最大值。刚看到这个题，很多人第一反应是Floyd，毕竟“任意两点最短路径”嘛，但仔细一看边权有十万级别，Floyd根本跑不动。这道题藏在朴素想法背后的考点，其实是两个：第一，能不能把树上任意点对的异或路径转化成所有点到根的异或值；第二，能不能用二进制字典树在O(nlogn)内求出最大异或对。今天我把这道题的完整思路、证明、实现和踩坑记录都翻出来聊聊，如果你正在准备算法面试，或者想补一补位运算和树形结构的基础，这篇应该能帮上忙。

1. 题目来龙去脉与核心考点拆解

1.1 拿到题目时的第一反应

我当时是在一个算法训练营的题单里看到这道题的，记录名就叫“2024年题22”。题单里前21题都是常规的二叉树遍历、动态规划入门，突然蹦出这么一道树上的异或极值问题，说实话有点措手不及。题目给的样例很短，只有四个节点，但要求输出所有点对距离的最大异或值。

我的第一反应是枚举所有点对，然后跑LCA求路径异或和，但仔细一算，点对数量是O(n^2)，LCA预处理虽然能到O(logn)，整体还是O(n^2 logn)。当n到十万级别，这个复杂度就是天文数字，随便跑一组数据就要卡死。

这道题真正的难点不是“怎么求路径异或和”，而是“能不能避免枚举所有点对”。如果你以前接触过“最大异或对”那道经典题，可能会意识到这两者之间有某种联系。可要把树上路径和“最大异或对”扯上关系，需要先跨过一道关键的门槛。

1.2 题目真正想考察的四个能力

第一个能力是观察能力，你能不能看出路径异或和与根节点路径异或和之间的抵消关系。第二个能力是模型转化能力，把树上的路径距离问题转成一组数的最大异或对问题。第三个能力是数据结构设计能力，能不能写出正确的二进制字典树，搞清楚插入、查询、删除的边界。第四个能力是复杂度估算能力，不仅要会写代码，还要能算清楚空间开销和递归深度这类隐藏风险。

这四项能力正好对应了算法题里最常考的“数学观察 + 问题等价 + 高级数据结构 + 工程细节”。如果你只是背过字典树模板，但不知道它为什么能在这里用，面试官多追问一句“为什么要从高位开始贪心”，你很容易卡住。所以这篇文章不只是讲题解，更想把背后的判断逻辑说透。

1.3 几种常见做法为什么都行不通

先说Floyd算法。那是最自然的想法，树本身是一个稀疏图，Floyd是O(n^3)，n只要超过500基本就废了，更别说十万。就算你用Dijkstra求所有点对的最短路径，O(n^2 logn)依然不可接受，因为距离定义是异或和，边权非负但不存在单调性，没法用单源最短路径优化。

还有人会想到点分治。点分治确实能处理树上路径统计问题，比如统计路径长度小于等于k的数量，但那是针对可合并的路径长度，异或路径用点分治也能做，不过实现复杂度很高，要在每个分治重心维护子树的异或集合，而且写起来很容易出错。相比而言，根路径异或转化后加字典树的方案更简洁，编程复杂度低得多，也更容易调试。

提示：树上路径异或问题有一个通用结论：任意两点u、v之间的路径异或值 = dis[u] ^ dis[v]，其中dis[x]表示从根到x路径上边权的异或值。这个结论在所有关于树边权的异或问题里都适用。

2. 核心算法设计：从树上问题到字典树问题

2.1 关键一步：为什么路径异或能直接抵消公共部分

任取两个节点u和v，它们从根出发的路径在某些位置会发生分叉。假设分叉点为lca(u, v)，那么从根到u的路径异或值dis[u] = root到lca的异或值 ^ lca到u的异或值。同理，dis[v] = root到lca的异或值 ^ lca到v的异或值。

当我们做dis[u] ^ dis[v]时，root到lca的这段公共路径异或值会出现两次。异或运算有一个性质：a ^ a = 0，所以公共部分被完全抵消，剩下的正好就是lca到u的路径异或值加上lca到v的路径异或值，也就是u到v整条路径的异或值。这个过程不关心lca具体是哪个节点，所以只需要DFS一次，从根开始算出所有节点的dis，就能把任意点对的距离转化成两个dis值的异或。

我当时看到这个结论的时候觉得特别像“前缀和”的思想。普通数组里，区间和可以用前缀和相减得到，因为加法的逆运算是减法。树上的路径异或问题，对应的就是一个“异或前缀和”，因为异或的逆运算还是异或自己。想通这一层，整个题目的难度就降了一半。

2.2 二进制字典树是什么，怎么构建

字典树本身是一棵多叉树，通常用来存字符串，每个节点表示一个字符。二进制字典树是它的一个变体，每个节点只有两个儿子，分别代表二进制位0和1。我们把一个整数拆成31位或32位二进制串，从高位到低位依次插入字典树，这样每个叶子到根的路径就唯一对应一个数的二进制表示。

构建的时候，根节点是第0层，代表最高位。插入一个数字x时，从最高位开始，如果当前位是1就检查是否存在1儿子，没有就创建，然后下移到该儿子，继续处理下一位。为了支持查询最大异或值，需要在节点里额外记录一个cnt计数，表示当前子树中有多少个数字，这样在碰到动态插入和删除时也能处理。

空间上要注意一个陷阱：别看只有n个数字，每个数字位数是31，字典树节点数是n * 31 + 1。n是十万时，节点数最多310万左右。如果你开数组实现，每个节点有两个int类型的son，还有cnt，内存大概是310万 * 12字节，算下来约37MB，在不少竞赛平台的256MB限制下是足够的，但要小心别开成动态new节点，否则频繁分配内存既慢又容易爆。

2.3 为什么从高位到低位贪心是正确策略

查询最大异或值的时候，对于当前数字x，我们希望找到另一个数字y，使得x ^ y尽量大。异或值的大小主要由高位决定，这是二进制的常识：最高位不同，哪怕后面全布拉一堆1，也比不上最高位带来的2^(k)差距。

所以从最高位开始，如果x当前位是0，我们优先找当前位为1的兄弟节点，这样异或结果当前位就是1；如果x当前位是1，就优先找当前位为0的兄弟节点。只有优先想要的分支不存在时，才被迫走另一个分支。这种每一步取最优、不考虑后续影响的策略，在二进制异或场景下就是全局最优，因为它等价于逐位构造一个尽可能大的二进制数，不像背包问题那样存在后效性。

用不太严谨的生活类比：就像挑选一件商品时先比较百位数，百位数更大直接胜出，根本不需要看十位数和个位数。二进制异或的每一位权重都比后面所有位加起来还大，所以高位必须优先满足。

3. 完整实现与参数细节

3.1 数据结构定义与初始化写法

我习惯用数组实现字典树，虽然看起来不如结构体直观，但胜在速度稳定。核心数据有三个数组：son[N * 31][2]用于存左右儿子，cnt[N * 31]用于计数，root固定为0号节点。初始化时把son数组全部置0，cnt也置0。这里有个容易踩的坑：0号节点本身会被当作根节点，所以son[0][0]和son[0][1]初始必须是0，表示根节点还没有任何儿子。

DFS计算dis值时，需要前向星建图。每条边存to和w，再加一个next指针。数组大小至少是2 * n，因为树是无向图。第一遍DFS从根节点开始，把当前xor值往下传，每访问一条边就把边权异或进去。建议用栈模拟DFS，防止十万节点的链状树让递归栈溢出，虽然实际测试中很多环境下递归栈深度也能撑住，但用栈更稳妥。

3.2 DFS计算根路径异或值的两种写法

递归写法最简洁，核心代码如下：

void dfs(int u, int fa, int curXor) { dis[u] = curXor; for (int i = head[u]; i != -1; i = edge[i].next) { int v = edge[i].to; if (v == fa) continue; dfs(v, u, curXor ^ edge[i].w); } }

如果担心递归爆栈，换成显式栈写法也很快：

stack<int> stNode, stFa, stXor; stNode.push(1); stFa.push(0); stXor.push(0); while (!stNode.empty()) { int u = stNode.top(); stNode.pop(); int fa = stFa.top(); stFa.pop(); int x = stXor.top(); stXor.pop(); dis[u] = x; for (int i = head[u]; i != -1; i = edge[i].next) { int v = edge[i].to; if (v == fa) continue; stNode.push(v); stFa.push(u); stXor.push(x ^ edge[i].w); } }

注意：递归写法的终止条件除了v == fa，还有一个隐含条件。如果树以1号节点为根，根本没有父节点，所以fa初始传0。建图时节点编号从1开始，0号节点预留为不存在的节点，这样fa=0就不会与真实节点冲突。

3.3 字典树插入与查询的代码实现

插入操作要从数字的最高位开始。这里我约定处理31位，也就是从第31位到第0位，覆盖2^31以内的非负整数。如果题目给的权值范围可能到2^31以上，就要相应扩大到32位或更多。判断某一位是0还是1，用(x >> i) & 1来取。

void insert(int x) { int u = 0; for (int i = 30; i >= 0; i--) { int bit = (x >> i) & 1; if (!son[u][bit]) { son[u][bit] = ++tot; // 新节点的son和cnt默认是0，这里只需把tot自增 } u = son[u][bit]; cnt[u]++; } }

查询与x异或值最大的数，核心逻辑是优先走相反位。如果相反位的子树cnt大于0，说明存在数字可以在这位让异或结果为1，累加答案的增长值；否则只能走相同位。答案的累加方式是ans = ans | (1 << i)，意思是把第i位置为1。

int query(int x) { int u = 0, res = 0; for (int i = 30; i >= 0; i--) { int bit = (x >> i) & 1; int want = bit ^ 1; if (son[u][want] && cnt[son[u][want]]) { res |= (1 << i); u = son[u][want]; } else { u = son[u][bit]; } } return res; }

这里有一个初学者容易忽略的细节：插入时我们在路径上的每个节点都做了cnt[u]++，查询时判断的是son[u][want]这个位置是否存在且cnt大于0。如果数字被删除过，cnt会变成0，但son指针还在，所以必须加上cnt判断，否则会查到已经不存在的数字。

3.4 主流程复杂度分析

主流程可以分为三段：DFS算dis值是O(n)，把所有dis插入字典树是O(n * 31)，对每个dis查询最大异或值是O(n * 31)。总复杂度O(n * 31)，在n等于十万时大约运行三百万次操作，任何语言都能轻松通过。

空间方面，dis数组需要n+1个int，字典树数组大约需要三百一十万个节点，每个节点两个int和一个int的计数，总计930万个int，约37MB。内存是富余的，但如果你用vector动态扩容，可能因为频繁push_back导致开销变大，推荐直接用固定数组。

从实现角度看，这道题的代码量不大，难点在于你能否一次性把边界条件写对。比如根节点0的初始化、DFS的父节点判断、字典树tot变量是否从0开始、查询时cnt的判断、位数的上限。这些细节我在第四部分会展开讲一讲。

4. 手把手模拟运行与踩坑记录

4.1 用一个小规模样例手动推演

回到题目给的简单例子。四个节点，边权分别是1、2、4。从根1出发，DFS后得到dis[1] = 0，dis[2] = 1，dis[3] = 2，dis[4] = 1 ^ 4 = 5。把这四个数逐个插入字典树。

假设只处理3位二进制，0的二进制是000，1是001，2是010，5是101。插入后查询：

• 查dis[1] = 0，字典树中最希望走相反位1，最高位为1的只有5，所以异或结果是0 ^ 5 = 5。
• 查dis[2] = 1，最高位希望碰到1，只有5，异或结果是1 ^ 5 = 4。
• 查dis[3] = 2，最高位希望碰到1，只有5，异或结果是2 ^ 5 = 7。
• 查dis[4] = 5，字典树里最高位为0的数有0、1、2，其中0 ^ 5 = 5，1 ^ 5 = 4，2 ^ 5 = 7，最大是7。

所以最终输出7。这个结果和直接枚举点对是一样的，但整个过程没有真正枚举所有点对，只是把每个dis查了一遍。

4.2 我在测试中遇到的三类典型Bug

第一类Bug是数组开小了。我一开始字典树数组开成n * 30，结果在数据稍微大一点的时候越界，本地跑样例没问题，一上评测就报Runtime Error。原因是每个数字插入需要31个节点，n个数字最多n * 31个新节点，而且如果根节点第0层也算一个节点，节点数上限是n * 31 + 1。保险起见直接开成n * 31 + 5，或者干脆开n * 32，省得再算。

第二类Bug是DFS时的异或结果没有继续传给下一层。刚练习的时候我把dis[u]算好之后，子节点的curXor写成0而不是curXor ^ edge[i].w，导致后面的点全错了。这种错误在调试时非常隐蔽，因为小样例可能碰巧能过，比如当边权都是0的时候输出0，你根本看不出问题。

第三类Bug是查询时没有判断cnt。当时写了一个支持删除数字的版本，删除时把路径上的cnt减一，但查询逻辑还在用旧的判断条件，结果查到了已经删除的数字。正确做法是查询时不仅要看son指针是否存在，还要确认cnt[son[u][want]]大于0。

4.3 剪枝与优化的实测心得

这道题本身不需要太复杂的剪枝，但有一个优化思路值得尝试：如果某个节点的两个儿子都不存在，说明这个位置没有插入数字，查询时可以提前终止。不过对于固定31位的循环，提前终止的判断反而会引入分支，性能提升很有限，我实测下来不如直接循环完，省得判断出错。

另一个实测心得是DFS用数组模拟栈确实比递归快不少，尤其是在链状树数据下。递归写法在栈空间紧张的环境中可能直接栈溢出，而显式栈虽然代码稍微长一点，但稳定性好得多。如果你是在比赛环境中，建议直接用显式栈，这也是我的习惯。

还有一个小优化：当n等于1时，只有根节点自己，所有点对距离都是0，可以直接输出0，避免插入查询过程产生问题。这个边界别忘了。

5. 相似题目变种与学习路线建议

5.1 三个容易混淆的变种题

第一类变种是“求树上两点之间路径异或值等于k的路径数量”，这就不是求极值，而是统计数量。思路依然先用dis数组转换，但后面的查询要改成“在字典树中统计等于某个值的数量”，核心是维护每个节点的cnt并做计数查询。

第二类变种是“求数组任意两个数字异或小于等于k的对数”，这就变成纯粹的字典树加计数统计，没有树上部分，适合当作基础练手。做法是逐个插入数字，每次查询时统计当前字典树中与当前数字异或结果小于等于k的数字个数。

第三类变种是“求树上路径和的最大子段异或值”，和原题不同，它不是点对距离，而是一条路径内部所有边权异或的最大连续子段，这需要结合点分治和可持久化字典树，难度明显上一个台阶。

如果你把原题吃透了，上面这三个变种都只需要在原思路的基础上加点细节就行，不会完全无从下手。这也是为什么我说这道题很有练习价值，它一个模型能串联起好多考点。

5.2 从这道题延伸出的算法学习路径

如果你是因为这道题第一次接触字典树，我建议你按这个顺序补课。先做一道“数组中找出两个数的最大异或值”，这是纯粹的字典树极值，没有任何树形结构，适合熟悉插入和查询。再做“统计异或值为k的对数”，学会在查询中计数。接着回到这道树上题，理解dis数组和前缀和的对应关系。之后可以尝试可持久化字典树，解决区间异或极值问题。

学习过程中要注意一个陷阱：不要以为会了字典树模板就等于会了这道题。题目真正的灵魂在于“dis[u] ^ dis[v]”这个等价转化，字典树只是最后一步的执行工具。如果你只是背模板而不理解为什么可以转成数组最大异或对，换个类似的树题还是会卡住。

5.3 竞赛与面试中的时间和心态管理经验

我见过不少人在这种题上栽跟头，不是不会做，而是第一步就想偏了。看到树、路径、最大这些关键词，脑子立刻被Floyd和点分治占据，绕了一圈才发现根本用不上。所以我的建议是：先别急着写代码，花两分钟把已知条件写在草稿纸上，想一想有没有什么数学性质可以化简。

在面试场景里，这道题二十到三十分钟内应该能完成从思路到代码。如果你能先把“dis数组等价转化”这个关键点说出来，面试官通常就会觉得你已经抓住了核心，后面代码写慢一点反而没有太大问题。比赛场景则是另一个逻辑，需要在暗时间的约束下快速完成，建议把字典树模板提前准备好，比赛时直接复用。

提示：真正到了赛场上，输入规模大的时候建议关闭同步流，用scanf或快速IO读取，否则光输入一个十万边的树就可能吃掉一大半时间。

最后再说一个我个人的小心得。做完这道题之后，我特意针对“树上路径异或”这个模型整理了一页笔记，把dis数组的转化、字典树的模板、还有各种变种的关键判断都写在上面。后来遇到好几道类似的题，基本都能在几分钟内定位到同一个套路。这就是训练算法的价值，它不只是积累一道题，而是积累一类问题的识别能力。下次你看到“树+异或+极值”，希望也能像我一样，脑子里先亮起dis数组和字典树这两盏灯。