树上的查询不一定需要复杂数据结构。更重要的是先看清：询问的是一条根路径、两点之间的行走，还是一群满足距离关系的点。本文用三题逐层增加工具，最后把“枚举所有点”变成“找中点、减去两边”。

学习顺序是 DFS 子树区间 → 倍增祖先与 LCA → 路径距离 → 奇偶性与分量计数。三份代码独立完整，均使用迭代遍历，避免长链触发递归栈风险。

学习路线与题目边界

先读 树上 DFS 三题 和 子树区间，再进入本文；若目标是每个根的整体答案，可对照 换根 DP 三题。LCA 不是换根 DP 的替代品，它主要回答固定树上两点的关系。

以下题名、难度、原始标签与约束于 2026-09-30 从 Codeforces 官方题目页核对。难度是平台标记，不代表三题对所有人都严格递增。

官方题目 难度 官方标签 本文抓手
1328E Tree Queries 1900 dfs and similar, graphs, trees 全部上移一层后是否共链
1304E 1-Trees and Queries 2000 data structures, dfs and similar, shortest paths, trees 三种路线长度与奇偶性
519E A and B and Lecture Rooms 2100 binary search, data structures, dfs and similar, dp, trees 中点两侧分量的补集
题目 核心规模 不能忽略的条件
1328E 2 ≤ n ≤ 200000；1 ≤ m ≤ 200000；所有询问点数之和 ≤ 200000 根为 1；同一询问内顶点互异
1304E 3 ≤ n ≤ 100000；1 ≤ q ≤ 100000；1 ≤ k ≤ 1000000000 新边连接不同且原本不相邻的点；可重复走边；询问独立
519E 1 ≤ n ≤ 100000；1 ≤ m ≤ 100000 两个查询点允许相同；距离按边数计

第一题 1328E 把靠近路径改写为祖先关系

为什么只看父节点就够了

问题要求存在一条从根出发的路径，使每个给定点到这条路径的距离不超过 1。直接枚举路径终点，再逐个算距离，最坏会重复处理整棵树。

令根的父节点仍为根，将每个查询点 v 换成 parent[v]。原条件等价于：这些父节点都在某条根路径上。

必要性：若 v 在合法路径上，它的父节点也在路径上；若 v 不在路径上但与路径相邻，邻接的只能是 v 的父节点。假如邻接的是 v 的孩子，根到孩子的路径本来就经过 v，与“不在路径上”矛盾。

充分性：若所有 parent[v] 都在路径上，每个原点 v 就在路径上或与路径相邻。上移不是要求真实移动顶点，而是把存在性条件换成更易检查的关系。

最深父节点决定唯一的候选链

在上移后的点中选深度最大的 w。它们共处一条根路径，当且仅当每个点都是 w 的祖先。相同深度的两个不同点不能互为祖先，因此选谁都不会掩盖冲突。

DFS 先序中，v 的子树恰好占据半开区间 [tin[v], tin[v]+size[v])。于是 v 是 w 的祖先，当且仅当 w 的进入编号落在该区间内。这里包含“自己是自己的祖先”。

手算一次分支冲突

自建树的边为 1—2、1—3、2—4、2—5、3—6，根为 1。

原查询点 上移后的点 最深点 结果
4、5 2、2 2 YES，可取根到 2 的路径
4、6 2、3 2 或 3 NO，两条分支无法共链
1、4、3 1、2、1 2 YES，根留在根
6 3 3 YES，单点总可满足
实现细节 不变量
栈模拟 DFS，弹出时记录 tin 一棵子树被完整访问后才轮到兄弟子树
逆先序累计 size 孩子的计数先加入父节点
根的 parent 设为 1 查询包含根时无需访问虚构的 0 号节点
比较区间右端使用严格小于 半开区间不包含下一个子树

完整 C++17 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<vector<int>> g(n + 1);
    for (int i = 1, a, b; i < n; ++i) {
        cin >> a >> b;
        g[a].push_back(b); g[b].push_back(a);
    }
    vector<int> par(n + 1), dep(n + 1), tin(n + 1), sz(n + 1, 1);
    vector<int> order, st{1};
    par[1] = 1;
    while (!st.empty()) {
        int v = st.back(); st.pop_back();
        tin[v] = static_cast<int>(order.size());
        order.push_back(v);
        for (int u : g[v]) if (u != par[v]) {
            par[u] = v; dep[u] = dep[v] + 1;
            st.push_back(u);
        }
    }
    for (int i = n - 1; i > 0; --i) {
        int v = order[i];
        sz[par[v]] += sz[v];
    }
    while (m--) {
        int k; cin >> k;
        vector<int> shifted(k);
        int deepest = 1;
        for (int &v : shifted) {
            cin >> v; v = par[v];
            if (dep[v] > dep[deepest]) deepest = v;
        }
        bool ok = true;
        for (int v : shifted)
            if (!(tin[v] <= tin[deepest] && tin[deepest] < tin[v] + sz[v]))
                ok = false;
        cout << (ok ? "YES" : "NO") << '\n';
    }
}

预处理时间与空间均为 O(n)，所有查询时间为 O(Σk)。这题无需为“可能用到”而建立 O(n log n) 的 LCA 表。

共用工具 倍增祖先和最近公共祖先

第二、三题需要快速计算任意两点距离。若每次沿父指针逐步向上，长链上一次查询就会花 O(n)。

定义 up[j][v] 为 v 的第 2^j 个祖先，深度 dep[1]=0。根以上仍停在根。转移是 up[j][v]=up[j−1][up[j−1][v]]，即跳两段相同长度。

要做的操作 方法 单次复杂度
向上跳 s 条边 将 s 按二进制拆开 O(log n)
求 LCA(a,b) 先抬平深度，再从大到小同时跳 O(log n)
求距离 dep[a]+dep[b]−2dep[LCA(a,b)] O(log n)
求子树大小 按父先子后的遍历顺序逆序汇总 全树 O(n)

LCA 同跳阶段只在两个 2^j 祖先不同时跳跃。此时双方仍严格位于最近公共祖先下方；大步都不能再跳后，两者的父节点就是 LCA。先处理抬平后两点重合的情况，否则祖先与后代的查询会出错。

例如上面的六点树：LCA(4,5)=2，距离为 2+2−2×1=2；LCA(4,6)=1，距离为 2+2−0=4。向上跳 13 层则可拆成 8+4+1，并不需要循环走 13 次。

代码中的共用 Tree 结构使用父先子后的迭代顺序构建深度和子树大小。这个顺序不用于 DFS 区间判定；第一题的 tin 必须来自真正的 DFS，不能用广度优先顺序冒充。

第二题 1304E 恰好走 k 步不等于最短路

每个询问临时增加无向边 x—y，问能否从 a 走到 b，恰好使用 k 条边。这里允许重复经过点和边，所以研究的是行走，不是简单路径。新增边在下一次询问中不保留。

三个长度不能只留下最小值

不必重新建图跑 BFS。只计算：

候选 长度 含义
d0 dist(a,b) 不使用新边
d1 dist(a,x)+1+dist(y,b) 经 x 到 y 使用新边
d2 dist(a,y)+1+dist(x,b) 经 y 到 x 使用新边

这三种路线都是真实可走的，即使两段树路径有重叠也没有关系。对于某个长度 d，只要 d≤k 且 k−d 为偶数，就可以沿一条边来回走若干次补足长度。n≥3 保证不会遇到无边可绕的单节点树。

为什么这样也没有漏掉其他可能？加一条边后图中只有一个环。对任意合法行走，先去掉沿边往返的片段，每次删去 2 步；在唯一环上多绕两整圈也可删去，减少的长度仍为偶数。保留至多一次绕环后，新边至多使用一次，余下树上的绕行也都能按偶数步消去。对应的基础路线就是上述三种之一。因此至少存在一个候选，不长于原行走且同奇偶。

也可以从奇偶理解：偶数长度的环不能改变树路径的奇偶；奇数长度的环能够改变奇偶，但绕到环上同样需要成本，不能只看 k 大不大。

一条短链说明为什么要检查三个候选

原树为 1—2—3—4—5，临时加入 1—3，查询 a=1、b=2。三个长度分别是 d0=1、d1=2、d2=4。

k 可用候选 答案 理由
1 d0=1 YES 直接到达
2 d1=2 YES 1→3→2
3 d0=1 YES 比直接路线多两步
4 d1=2 或 d2=4 YES 可补两步或直接选四步路线

若只取最短值 1，再检查奇偶，会错误拒绝 k=2。另一个对照：加入 1—4、查询 1 到 3，三个长度为 2、2、6；k=3 时全部不合格，虽然最短距离只有 2。

完整 C++17 实现

下面包含完整倍增结构，可独立提交，不依赖上一份代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <bits/stdc++.h>
using namespace std;

struct Tree {
    int n, lg;
    vector<vector<int>> g, up;
    vector<int> dep, sz;
    explicit Tree(int size) : n(size), lg(1), g(n + 1),
        dep(n + 1), sz(n + 1, 1) {
        while ((1LL << lg) <= n) ++lg;
        up.assign(lg, vector<int>(n + 1, 1));
    }
    void add(int a, int b) { g[a].push_back(b); g[b].push_back(a); }
    void build() {
        vector<int> order{1};
        up[0][1] = 1;
        for (size_t i = 0; i < order.size(); ++i) {
            int v = order[i];
            for (int u : g[v]) if (u != up[0][v]) {
                up[0][u] = v;
                dep[u] = dep[v] + 1;
                order.push_back(u);
            }
        }
        for (int j = 1; j < lg; ++j)
            for (int v = 1; v <= n; ++v)
                up[j][v] = up[j - 1][up[j - 1][v]];
        for (int i = n - 1; i > 0; --i) {
            int v = order[i];
            sz[up[0][v]] += sz[v];
        }
    }
    int jump(int v, int steps) const {
        for (int j = 0; j < lg; ++j)
            if ((steps >> j) & 1) v = up[j][v];
        return v;
    }
    int lca(int a, int b) const {
        if (dep[a] < dep[b]) swap(a, b);
        a = jump(a, dep[a] - dep[b]);
        if (a == b) return a;
        for (int j = lg - 1; j >= 0; --j)
            if (up[j][a] != up[j][b]) {
                a = up[j][a]; b = up[j][b];
            }
        return up[0][a];
    }
    int dist(int a, int b) const {
        return dep[a] + dep[b] - 2 * dep[lca(a, b)];
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n; cin >> n;
    Tree t(n);
    for (int i = 1, a, b; i < n; ++i) {
        cin >> a >> b; t.add(a, b);
    }
    t.build();
    int q; cin >> q;
    while (q--) {
        int x, y, a, b;
        long long k;
        cin >> x >> y >> a >> b >> k;
        array<long long, 3> length{
            t.dist(a, b),
            t.dist(a, x) + 1LL + t.dist(y, b),
            t.dist(a, y) + 1LL + t.dist(x, b)
        };
        bool ok = false;
        for (long long d : length)
            if (d <= k && (k - d) % 2 == 0) ok = true;
        cout << (ok ? "YES" : "NO") << '\n';
    }
}

预处理 O(n log n)，每个询问只做常数次 LCA，总时间 O((n+q)log n)，空间 O(n log n)。k 最大为 10^9，代码用 long long 保存候选与差值，避免后续扩展约束时混用整数类型。

第三题 519E 等距点是中点两侧之外的所有点

给定 a、b，要数出多少顶点 z 满足 dist(z,a)=dist(z,b)。逐点做两次距离查询仍要 O(n log n)，无法承受十万次询问。

从路径投影证明中点条件

树上任意 z 通向 a、b 的路径，会在 a—b 路径上的某个点 p 分开。两个距离都包含 dist(z,p)，相减后只剩 dist(p,a)−dist(p,b)。所以 z 是否等距，只取决于它接入 a—b 路径的位置是不是正中点。

先分三种情况：

情况 结论 原因
a=b n 每个点到同一个端点的距离当然相同
dist(a,b) 为奇数 0 中点落在边内，不是顶点
正的偶数距离 找到顶点中点 mid 保留接入点为 mid 的所有分支

令距离 d=2h。从中点沿路径向 a、b 各走一步，会进入两个不同分量；这些点分别离一个端点更近，都应排除。其余点包括中点自身与旁支，正好等距。

为什么有两条计数公式

若 dep[a]=dep[b]，中点就是它们的 LCA。令 ca=jump(a,h−1)、cb=jump(b,h−1)，它们是中点朝两个端点方向的孩子。答案为 n−size[ca]−size[cb]。中点上方的整块区域也等距，因此不能只在中点的子树中数。

若深度不同，交换后让 a 更深。中点必在从 a 向上走 h 步的位置，且位于 LCA 的严格下方。令 mid=jump(a,h)、child=jump(a,h−1)。朝 b 的分量就是 mid 子树之外的区域；朝 a 的分量是 child 子树。剩下 size[mid]−size[child]。

六点树上的查询 中点或距离 手算结果
4、5 中点 2，扣掉子树 4 和 5 6−1−1=4，点为 1、2、3、6
4、6 中点 1，扣掉子树 2 和 3 6−3−2=1，只剩 1
1、4 中点 2，深度不同 size[2]−size[4]=3−1=2，点为 2、5
2、6 距离 3 0
3、3 相同点 6

完整 C++17 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include <bits/stdc++.h>
using namespace std;

struct Tree {
    int n, lg;
    vector<vector<int>> g, up;
    vector<int> dep, sz;
    explicit Tree(int size) : n(size), lg(1), g(n + 1),
        dep(n + 1), sz(n + 1, 1) {
        while ((1LL << lg) <= n) ++lg;
        up.assign(lg, vector<int>(n + 1, 1));
    }
    void add(int a, int b) { g[a].push_back(b); g[b].push_back(a); }
    void build() {
        vector<int> order{1};
        up[0][1] = 1;
        for (size_t i = 0; i < order.size(); ++i) {
            int v = order[i];
            for (int u : g[v]) if (u != up[0][v]) {
                up[0][u] = v;
                dep[u] = dep[v] + 1;
                order.push_back(u);
            }
        }
        for (int j = 1; j < lg; ++j)
            for (int v = 1; v <= n; ++v)
                up[j][v] = up[j - 1][up[j - 1][v]];
        for (int i = n - 1; i > 0; --i) {
            int v = order[i];
            sz[up[0][v]] += sz[v];
        }
    }
    int jump(int v, int steps) const {
        for (int j = 0; j < lg; ++j)
            if ((steps >> j) & 1) v = up[j][v];
        return v;
    }
    int lca(int a, int b) const {
        if (dep[a] < dep[b]) swap(a, b);
        a = jump(a, dep[a] - dep[b]);
        if (a == b) return a;
        for (int j = lg - 1; j >= 0; --j)
            if (up[j][a] != up[j][b]) {
                a = up[j][a]; b = up[j][b];
            }
        return up[0][a];
    }
    int dist(int a, int b) const {
        return dep[a] + dep[b] - 2 * dep[lca(a, b)];
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n; cin >> n;
    Tree t(n);
    for (int i = 1, a, b; i < n; ++i) {
        cin >> a >> b; t.add(a, b);
    }
    t.build();
    int q; cin >> q;
    while (q--) {
        int a, b; cin >> a >> b;
        if (a == b) { cout << n << '\n'; continue; }
        int d = t.dist(a, b);
        if (d % 2) { cout << 0 << '\n'; continue; }
        int half = d / 2;
        if (t.dep[a] == t.dep[b]) {
            int ca = t.jump(a, half - 1);
            int cb = t.jump(b, half - 1);
            cout << n - t.sz[ca] - t.sz[cb] << '\n';
        } else {
            if (t.dep[a] < t.dep[b]) swap(a, b);
            int mid = t.jump(a, half);
            int child = t.jump(a, half - 1);
            cout << t.sz[mid] - t.sz[child] << '\n';
        }
    }
}

预处理 O(n log n)，每次查询 O(log n)，空间 O(n log n)。根可以任取，因为无根树上的距离和等距关系不会因预处理根改变；两条公式只是采用根为 1 时的子树表达。

边界清单与独立验证

容易出错的地方 后果 检查方式
把 BFS 顺序当 DFS 先序 子树区间混进其他分支 让兄弟各自带孩子
1328E 检查原点必须共链 误拒绝合法的相邻旁支 查询兄弟叶子
1304E 只看最短候选 丢失另一个奇偶类 三角环上的二步查询
1304E 永久加入新边 下一询问不再是题目规定的图 同一原树切换不同新边
519E 漏掉相同端点 h−1 变成负数 查询 a=a，包括 n=1
519E 相同深度只数中点子树 漏掉中点上方的等距点 查询同一深层父节点的孩子
用递归遍历十万级长链 可能栈溢出 极限长链运行
把边数与点数混用 中点偏移一格 距离 2 的最小非平凡查询

专项程序从本文抽取三段 C++17，使用 -O2 -Wall -Wextra -pedantic 编译。参考答案不使用文章的 LCA 或计数公式：

本次三份程序均无警告编译，通过 744 次执行和 581,896 个查询结果核验；其中 246 棵小树包含 1 至 5 个点的全部标号树及固定种子的随机树，另有最大规模链、星形树和最大步数测试。

题目 独立参考方法
1328E 枚举每个路径终点，显式构造根路径，再检查每个查询点到路径的最小 BFS 距离
1304E 临时建图，逐步扩展恰好第 t 步可到达的顶点集合
519E 从每个点 BFS，逐个比较到两个端点的距离
极限规模 链与星形的闭式答案，以及最大 k 的奇偶边界 
1
node tests/verify-tree-queries-three-article.cjs

从这三题带走的不是三条孤立公式：先确定“可替代的条件”，再选择祖先判断或 LCA；最后把树的唯一通路转成奇偶约束或分量计数。回到 算法练习路径，可以继续比较 并查集离线查询 与 线段树区间摘要，分清不同查询模型需要维护的信息。