先交代一下背景：最近在补树的进阶题单时，又翻到了 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、加边，第 i+1 次询问时这棵树一定要回到原样。实际操作中，我们压根不需要真的把边加进图里，只需要在原树上把几种可能的距离算出来就行。这两个限制结合，才是整道题设计的核心。
1.2 “恰好 k”的本质是奇偶性
在一般无向图里，判断是否存在长度恰好为 k 的路径，这类问题有个非常通用的暴力思路：把一条边走过去再原路走回来，路径总长度增加 2，并且起点终点不变。
举个具体例子，假设你已经找到一条从 a 到 b 的路径，长度是 d。如果 k 比 d 大，但 k 和 d 的差值是偶数，那么你可以在路径中间挑一个点，走向它的某个邻居，再立刻走回来，每做一次这个操作路径长度就加 2。重复操作，就可以把长度从 d 逐步变成 d+2、d+4，一直到 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)+1+dist(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 在不同子树里，深度差就完全不能代表实际路径长度。
比如一棵树根是 1，2 和 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; vector<int> 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 开到 2e5，20 仍然足够；开到 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) 算出来，整道题的复杂度瞬间就清晰了。如果你刚做完这道题，可以顺手把类似的原树加边后求最短路径的题拿来做对比，会发现很多题目都是套着各种壳子在考同一个思想。
