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数组全部置0cnt也置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); } }如果担心递归爆栈换成显式栈写法也很快stackint 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号节点预留为不存在的节点这样fa0就不会与真实节点冲突。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数组需要n1个int字典树数组大约需要三百一十万个节点每个节点两个int和一个int的计数总计930万个int约37MB。内存是富余的但如果你用vector动态扩容可能因为频繁push_back导致开销变大推荐直接用固定数组。从实现角度看这道题的代码量不大难点在于你能否一次性把边界条件写对。比如根节点0的初始化、DFS的父节点判断、字典树tot变量是否从0开始、查询时cnt的判断、位数的上限。这些细节我在第四部分会展开讲一讲。4. 手把手模拟运行与踩坑记录4.1 用一个小规模样例手动推演回到题目给的简单例子。四个节点边权分别是1、2、4。从根1出发DFS后得到dis[1] 0dis[2] 1dis[3] 2dis[4] 1 ^ 4 5。把这四个数逐个插入字典树。假设只处理3位二进制0的二进制是0001是0012是0105是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 51 ^ 5 42 ^ 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数组和字典树这两盏灯。