树上加边后的路径存在性判断：LCA与奇偶性分析

先交代一下背景最近在补树的进阶题单时又翻到了 Codeforces 1304E 这道老题。题面很短五六十行就完事了但评论区里总能看到不少人在抱怨“看到了 LCA 标签还是不会做”。我一开始也有点恼火因为这道题表面上问的是“往树上临时加一条边之后存不存在一条长度恰好为 k 的路径”核心套路却非常清晰树上距离 奇偶性判断。如果你正好在练 LCA、倍增、树上问题或者想搞明白“允许重复走边后的路径存在性”这一类题那这题值得完完整整推一遍。1. 题目到底问什么1-Tree 不是“一棵树”1.1 每轮询问都是一次临时加边先把题意复述得准确一点。给一棵 n 个点的树每条边权都是 1。接下来有 q 次询问每次询问给五个参数 x、y、a、b、k。所谓 1-Tree就是假设在原本的树上临时加上一条 x 到 y 的边形成一个新的图。这个图本质上是一棵树多了一条边所以图里恰好有一个环名字里的“1”指的就是“加一条边”。要回答的问题是在这个临时加边后的图里从 a 到 b 是否存在一条长度恰好为 k 的路径。关键限制有两个很多新手会因为忽略它们而卡很久。第一个限制是路径允许重复经过边和点不是一定要走简单路径。这一点让“恰好为 k”变得有操作空间因为你可以通过在某条边上反复横跳来增加长度。第二个限制是每次询问之间的加边互相独立也就是说第 i 次问了 x、y、加边第 i1 次询问时这棵树一定要回到原样。实际操作中我们压根不需要真的把边加进图里只需要在原树上把几种可能的距离算出来就行。这两个限制结合才是整道题设计的核心。1.2 “恰好 k”的本质是奇偶性在一般无向图里判断是否存在长度恰好为 k 的路径这类问题有个非常通用的暴力思路把一条边走过去再原路走回来路径总长度增加 2并且起点终点不变。举个具体例子假设你已经找到一条从 a 到 b 的路径长度是 d。如果 k 比 d 大但 k 和 d 的差值是偶数那么你可以在路径中间挑一个点走向它的某个邻居再立刻走回来每做一次这个操作路径长度就加 2。重复操作就可以把长度从 d 逐步变成 d2、d4一直到 k。如果 k 和 d 的差值是个奇数那无论你怎么来回走长度都不会变成 k因为每次增加的量都是偶数奇偶性永远不会翻转。所以这道题的判断就转换成了在加边后的图里算出从 a 到 b 的最短距离 mn。若存在长度为 k 的路径前提必须是 mn k 并且 (k - mn) 是偶数。反过来只要 mn k 且奇偶性一致就一定有办法通过反复走长度为 2 的回路把路径长度调整到 k。这样一来原来很抽象的“恰好长度”就变成了一个“最短距离 奇偶校验”的问题这也是整题能使用 LCA 的根本原因。2. 加一条边后两点之间的最短距离只有三种候选2.1 分类讨论走不走这条新边现在的问题变成临时加了边 (x, y) 之后a 到 b 的最短距离到底怎么算。熟悉树的人第一反应肯定是分两类讨论。第一类路径不经过新加的边那这条路径就是原树上 a 到 b 的唯一简单路径距离记作 d1 dist(a, b)。第二类路径经过新加的边。由于新边连接的是 x 和 y所以任何经过它的路径必然可以先从 a 走到 x跨过新边到 y再从 y 走到 b。距离就是 dist(a, x) 1 dist(y, b)。方向也可以反过来即先从 a 走到 y跨过新边到 x再从 x 走到 b距离是 dist(a, y) 1 dist(x, b)。这里其实隐含了一个结论经过新边的简单路径枚举这两个方向就够了。因为一旦决定从 x 端进入新边、从 y 端出来那么 a 到 x 段和 y 到 b 段在原树上的最短路径都是唯一的不会再有别的绕法。所以加边后的图里a 到 b 的最短距离就是下面三个值的最小值d1 dist(a, b) d2 dist(a, x) 1 dist(y, b) d3 dist(a, y) 1 dist(x, b) mn min(d1, d2, d3)这里需要强调题目里的 x、y 不一定是原来树上直接相连的点。即使 x 和 y 在原树上已经相邻公式依然成立只是此时加的新边会和原边构成重边但计算时 dist(a, x)1dist(y, b) 仍然表示“走了这条新边”逻辑上没有冲突。2.2 为什么不需要枚举绕环更多次的路径有读者可能会问加边之后图里出现了一个环路径在环上绕两圈怎么办理论上确实存在更长的路径比如从 a 到 x过新边到 y然后再返回 x再经过新边去 y最后到 b。但这对于“最短距离”没有意义因为这类路径长度一定大于上面三个候选中的某一个不可能成为最小值的竞争者。我们在第一步已经把最短距离 mn 算出来了而判断路径存在性时用的是“最短距离 奇偶性”所以更长路径不需要枚举。再往深一层说任意从 a 到 b 的路径哪怕它绕了很多圈它的长度一定是某个候选最短距离再加上若干个偶数得到的。因为图中只有一条额外边所有绕行都可以分解成在某个地方往返走了两次。从染色的角度看你可以把原树黑白染色加上这条新边后奇偶性只取决于 a、b 两点在原树上的形态以及是否多跨了一次新边。因此三个候选距离的奇偶性已经覆盖了所有可能不会出现第四个奇偶性不同的最短候选。3. LCA 是算树上距离的唯一正确姿势3.1 倍增板子里的两个关键细节点要计算 dist(a, x)、dist(y, b) 这类树上任意两点距离必然要用到 LCA。树上的两点距离有一个非常经典的公式dist(u, v) depth[u] depth[v] - 2 * depth[lca(u, v)]这里 depth 是从根到该点的深度lca 是最近公共祖先。道理很简单把 u 到 v 的路径拆成 u 向上走到 lca再向下走到 v两段路径长度分别是 depth[u] - depth[lca] 和 depth[v] - depth[lca]加起来就是这个公式。求 LCA 的方式很多离线 Tarjan、树链剖分、倍增、RMQ 都可以。这道题 n 和 q 范围通常都是 1e5 级别我用倍增最省心。倍增的代码敲过很多遍但有两个细节点值得单独拿出来说。第一个是根节点的父亲设置。很多模板会把根节点的父亲设成 0然后在跳倍增数组时要特判。我更习惯把根的父亲设成它自己void dfs(int v, int p) { up[v][0] p; for (int j 1; j LOG; j) { up[v][j] up[ up[v][j - 1] ][j - 1]; } for (int to : g[v]) { if (to p) continue; depth[to] depth[v] 1; dfs(to, v); } }这样根节点的 up 数组永远指向自己后面跳倍增不会跳到 0 号空节点省掉一堆边界判断。不是所有人都喜欢这个写法但我实测下来它最不容易写挂。第二个细节点是“先对齐深度再一起上跳”。求 LCA 时如果两个点深度不同先用二进制分解把更深的一个提到同一深度然后再从大到小枚举倍增层级只有在 up[u][j] ! up[v][j] 时才同时跳。最后返回 up[u][0] 就是 LCA。这个流程错任何一个细节都会导致答案偏一个点。3.2 深度差不能用“两个点深度相减”代替树上距离我见过有人拿到这题后试图用 depth[a] - depth[b] 来判断距离这是典型的错误。depth 是相对根节点的深度两个点的深度差只能反映它们一个在另一个祖先链上时的纵向距离。一旦 a 和 b 在不同子树里深度差就完全不能代表实际路径长度。比如一棵树根是 12 和 3 分别是根的两个儿子depth[2] depth[3] 1但 dist(2, 3) 显然是 2而深度差是 0。你必须先求出 lca(2, 3) 1再用公式算出 2。所以这道题里面所有 dist 计算都必须老老实实走 getDist 函数这也是整个代码里调用最频繁的部分。4. 完整实现走一遍从预处理到每次询问4.1 代码逐段解释下面是我整理的完整 C 代码。代码风格偏向比赛写法重点不在精致封装而在够稳、够快、不易出错。#include bits/stdc.h using namespace std; const int N 100005; const int LOG 20; vectorint g[N]; int depth[N]; int up[N][LOG]; void dfs(int v, int p) { up[v][0] p; for (int j 1; j LOG; j) { up[v][j] up[ up[v][j - 1] ][j - 1]; } for (int to : g[v]) { if (to p) continue; depth[to] depth[v] 1; dfs(to, v); } } int lca(int u, int v) { if (depth[u] depth[v]) { swap(u, v); } int diff depth[u] - depth[v]; for (int j 0; j LOG; j) { if (diff (1 j)) { u up[u][j]; } } if (u v) { return u; } for (int j LOG - 1; j 0; j--) { if (up[u][j] ! up[v][j]) { u up[u][j]; v up[v][j]; } } return up[u][0]; } int getDist(int u, int v) { int w lca(u, v); return depth[u] depth[v] - 2 * depth[w]; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; for (int i 0; i n - 1; i) { int u, v; cin u v; g[u].push_back(v); g[v].push_back(u); } dfs(1, 1); int q; cin q; while (q--) { int x, y, a, b, k; cin x y a b k; int d1 getDist(a, b); int d2 getDist(a, x) 1 getDist(y, b); int d3 getDist(a, y) 1 getDist(x, b); int mn min(d1, min(d2, d3)); if (k mn (k - mn) % 2 0) { cout YES\n; } else { cout NO\n; } } return 0; }这段代码的逻辑非常线性读树DFS 预处理倍增表读询问算三个候选距离取最小值奇偶判断输出。核心部分加起来不到二十行剩下全是 LCA 模板。有个细节LOG 取 20 是因为 2 的 19 次方是 524288已经超过 1e5完全够用。如果题目 n 开到 2e520 仍然足够开到 3e5 的话建议取 20 到 21总归要保证最大深度小于 2 的 LOG 次方。DFS 递归深度在 n 1e5 的链状数据下可能会让某些平台栈溢出如果提交时发现 RE 且怀疑栈问题可以把 dfs 改成手写栈的迭代版本或者使用编译指令加大栈空间。多数竞赛环境对 1e5 深度的递归是能扛住的但保险起见链状数据可以先在本地测一发。4.2 复杂度与数据范围预处理时间 O(n log n)每个询问要调用 getDist 一共五次每次 getDist 内一次 lca 是 O(log n)所以单询问复杂度 O(log n)。总复杂度 O((n q) log n)。空间复杂度 O(n log n)主要是倍增表。这个复杂度对 1e5 级别的题目来说非常宽裕。如果以后遇到同样思路但 n、q 到 2e5 的题这个模板也照样能用。真正会卡时间的是那些把“加边”持久化、每次跑 Dijkstra 或者 BFS 的做法那会把单次询问做到 O(n log n)在 1e5 下必挂。5. 我踩过的三个坑说出来都是常见错误5.1 坑一把临时加边真的加进了图里第一次写这题我差点在每次询问时执行 g[x].push_back(y)、g[y].push_back(x)然后在加边后的图上 BFS 求距离。这样做逻辑上不假甚至能过样例但复杂度直接爆炸。更隐蔽的问题是如果忘了在后面把边删掉那么第二次询问开始图就完全不是题目要的状态了结果会越来越离谱。正确做法是只把原树建一次图所有询问都在原树的 getDist 上完成。新边只是答案计算里的一个“虚拟选项”体现在 d2 和 d3 公式里的那个 1 上。把这一点想通代码量瞬间少了一大截。5.2 坑二只判断了原树距离忽略了走新边的可能还有一种错法是只求 d1 dist(a, b)然后直接拿 d1 去跟 k 做奇偶判断。遇到一些刁钻数据例如 a、b 在原树上隔得很远但走新边能大幅度缩短路径时这种判断就会漏掉正确答案。这类错误的本质是少考虑了“1-Tree”这个题设。既然题目允许加一条边那么路径集合理应包含经过新边的路径。虽然有些数据下 d1 仍然是最短距离但你不能假设所有询问都满足这一点。我把 d2、d3 写全之后顺手把所有样例和手造数据测了一遍才终于把所有情况覆盖住。5.3 坑三奇偶判断的位置和数据类型我把判断写成 if (k mn (k - mn) % 2 0) 之前曾经写错过一个版本先算 (k - d1) % 2又算 (k - d2) % 2然后只要有一个满足就输出 YES。这在部分数据下会得到错误答案因为三个候选距离中d2 和 d3 可能非常大而真正的最短距离是小得多的 d1。比如 k 很大d1 和它有相同的奇偶性显然可以在最短路径上兜圈子凑长度但 d2 也许奇偶性不符甚至比 k 还大。如果你错误地要求每个候选都必须满足条件或者错误地用“任意候选满足”替代“最短距离满足”都会把正确结果判错。记住结论只需要取 mn min(d1, d2, d3)然后判断 k mn 和 (k - mn) % 2 0。另外k 和距离虽然题目一般给在 int 范围内但我在比赛里已经养成习惯凡是涉及 k - mn 这种减法都用 long long 去接避免某些边界数据的减法溢出。虽然这题可能用不到但好习惯能省掉很多不必要的 Debug 时间。5.4 坑四只考虑 d2 dist(a,x) 1 dist(y,b)落掉反向 d3最后补一个很容易肉眼漏掉的坑。很多人推公式时推到了 d2就潜意识里以为经过新边的方案只有一种方向于是只写了一个方向。但加边是无向的从 a 先到 y、再经新边到 x、最后到 b 是完全独立的一条路径。单独推 d2 或单独推 d3 都可能恰好踩中错误数据。我当时写完后检查样例特意构造了 x 和 y 到 a、b 距离不对称的数据来验证。最后把 d3 加进去才让三个候选距离齐全。这个错误不靠造数据很难发现因为样例往往比较温和。6. 同类问题的变形思路从 1-Tree 延伸到更一般的路径存在性6.1 如果题目要求只能走简单路径明白这道题之后你可能会好奇如果题目改成“是否存在长度恰好为 k 的简单路径”答案会怎么变。那就不能简单地用最短距离 奇偶性了因为简单路径的长度是有限的而上来回走制造偶数增量的技巧不再合法。此时需要枚举候选简单路径分析每条路径的长度区间以及这个区间内满足奇偶性的长度有哪些。这一类问题通常会涉及到树的直径、路径拼接、甚至树分治。思路引导是好的但复杂度一般会高很多已经超出 1304E 的考察范围。刷题时遇到类似题建议先看数据范围再决定是否用“简单路径版”的解法。6.2 如果加两条边三个候选会变成更多候选继续延伸如果原树上临时加两条边图的环数变成两个那两点之间的候选最短路径会明显增多。直观地想每条新边都会带来两个方向的经过方案但新增两条边后路径还可能连续经过两条新边表达式会更复杂。这时候直接枚举路径形式的做法容易失控更通用的方法是把图建出来后在新图上跑 BFS 求最短路因为加了多条边之后用 LCA 枚举候选路径的组合数量可能是指数级的。1304E 之所以能用 LCA 优雅求解核心原因是“只加一条边”这个限制把候选路径压缩到了三个。这个限制一旦放宽算法就要换血。最后说一点个人体会这道题给我最大的收获不是 LCA 模板本身而是如何在树上快速分析“加一条边之后任意两点间路径集合”的变化。把“恰好 k”翻译成“最短距离 奇偶性”再配合 LCA 把树上距离 O(log n) 算出来整道题的复杂度瞬间就清晰了。如果你刚做完这道题可以顺手把类似的原树加边后求最短路径的题拿来做对比会发现很多题目都是套着各种壳子在考同一个思想。