仓鼠找 sugar

形式化题目

给定一棵 $n$ 个节点的树，给出 $q$ 次询问，每次询问给出四个节点 $a, b, c, d$ 。判断树上路径 $a \to b$ 与路径 $c \to d$ 是否至少共享一个节点，输出 Y 或 N。

思路

先看一个可以直接验证想法的朴素解：

cpp

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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-08-12 22:59
 * update_at: 2026-08-12 22:59
 */
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
// 每次询问先求出树上的父关系与深度，再：
//   1) 从 a 爬到 b，把路径 a-b 上的所有点标记为 1；
//   2) 从 c 爬到 d，沿途检查是否遇到被标记过的点。
// 每条路径用「两个端点同时向上爬」实现，复杂度 O(路径长度)，只适合小数据。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 105;

int n, q;
vector<int> g[MAXN]; // 树的邻接表
int parent[MAXN];    // parent[u] 表示 u 的父节点（根 1 的父节点是 0）
int depth[MAXN];     // depth[u] 表示 u 的深度
bool mark[MAXN];     // mark[u] = true 表示 u 在路径 a-b 上

// 从根 1 出发求父节点和深度（暴力爬路径需要）。
void get_parent() {
    queue<int> que;
    que.push(1);
    while (!que.empty()) {
        int u = que.front();
        que.pop();
        for (int v : g[u]) {
            if (v == parent[u]) continue;
            parent[v] = u;
            depth[v] = depth[u] + 1;
            que.push(v);
        }
    }
}

// 把路径 a-b 上经过的所有点标记为 true。
void mark_path(int a, int b) {
    int x = a, y = b;
    // 深的端点先单独向上爬，直到两个端点同深度。
    while (depth[x] > depth[y]) {
        mark[x] = true;
        x = parent[x];
    }
    while (depth[y] > depth[x]) {
        mark[y] = true;
        y = parent[y];
    }
    // 两个端点一起向上爬，爬到头时再标记相遇点。
    while (x != y) {
        mark[x] = true;
        mark[y] = true;
        x = parent[x];
        y = parent[y];
    }
    mark[x] = true;
}

// 从 c 爬到 d，检查路径上是否有被标记过的点（即与路径 a-b 相交）。
bool check_path(int c, int d) {
    int x = c, y = d;
    while (depth[x] > depth[y]) {
        if (mark[x]) return true;
        x = parent[x];
    }
    while (depth[y] > depth[x]) {
        if (mark[y]) return true;
        y = parent[y];
    }
    while (x != y) {
        if (mark[x] || mark[y]) return true;
        x = parent[x];
        y = parent[y];
    }
    return mark[x];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> q;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    get_parent();

    while (q--) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;

        fill(mark, mark + n + 1, false); // 清空上次标记
        mark_path(a, b);
        if (check_path(c, d))
            cout << "Y\n";
        else
            cout << "N\n";
    }

    return 0;
}

brute.cpp 每次询问先把路径 $a \to b$ 的所有点打上标记，再爬路径 $c \to d$ 检查碰撞，单次询问 $O(n)$ ，总复杂度 $O(nq)$ ，无法通过 $10^5$ 的数据。

关键观察有两个：

路径的最高点是 LCA：路径 $a \to b$ 上距根最近的点是 $p = \text{lca}(a,b)$ ，整条路径等于"从 $a$ 、 $b$ 分别爬到 $p$ "的两条链的并。
相交判定只看两个 LCA：两条路径相交当且仅当 $\text{lca}(a,b)$ 在路径 $c \to d$ 上，或 $\text{lca}(c,d)$ 在路径 $a \to b$ 上。如果交点存在，它必在某条路径的爬升段上，另一条路径的 LCA 必然落在这一段的祖先链里，从而在另一条路径上；反过来若某个 LCA 在对方路径上，它自己也必在己方路径上，交集显然非空。

于是问题退化成"判断一个点是否在某条路径上"。这可以用距离拆分等式：

\text{dist}(u, x) + \text{dist}(x, v) = \text{dist}(u, v)

恰好成立时 $x$ 在路径 $u \to v$ 上（树上路径唯一， $x$ 在岔路上时等式左边严格更大）。每次询问只需 $O(\log n)$ 次 LCA 调用，这就是"距离拆分"（rbook 文章《倍增求 LCA》中的路径包含模式）。

以样例的树为例（节点 1 为根，3 是 1 的儿子，4 的儿子是 2，2 的儿子是 5），对比两个典型询问：

text

询问	路径 $a \to b$	路径 $c \to d$	输出	判定过程
`2 2 1 4`	$\{2\}$	$\{1,4\}$	N	$\text{lca}(2,2)=2$ 不在路径 $1 \to 4$ 上， $\text{lca}(1,4)=1$ 不在路径 $2 \to 2$ 上
`4 1 3 4`	$\{4,1\}$	$\{3,1,4\}$	Y	$\text{lca}(4,1)=1$ 在路径 $3 \to 4$ 上，距离拆分 $0+1=1$ 成立

观察第二行：两个 LCA 都是 1，而第一行两个 LCA（2 和 1）互不在对方路径上，正好对应"共点"与"分离"两种结局。整个判定不需要构造路径点集，只比较常数个 LCA。

代码

cpp

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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-08-12 22:59
 * update_at: 2026-08-12 22:59
 */
// main.cpp：P3398 仓鼠找 sugar 正式解。
// 以 rbook 模板 lca-binary-lifting 为基底：倍增预处理祖先表，O(log n) 查询 LCA。
// 判断两条树上路径 a-b 与 c-d 是否相交：
//   1) 两条路径相交当且仅当 lca(a,b) 在路径 c-d 上，或 lca(c,d) 在路径 a-b 上；
//   2) 点 x 在路径 u-v 上当且仅当 dist(u,x) + dist(x,v) == dist(u,v)（距离拆分）。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;
const int LOG = 17; // 2^17 = 131072 > 1e5，按题目规模调整

vector<int> g[MAXN];      // 树的邻接表
int depth[MAXN];          // depth[u] 表示节点 u 的深度（根深度为 1）
int up[MAXN][LOG + 1];    // up[u][j] 表示节点 u 的 2^j 级祖先

// 预处理 depth 和倍增表 up[][]，fa 为父节点（根的父亲是 0）。
void dfs(int u, int fa) {
    up[u][0] = fa;
    depth[u] = depth[fa] + 1;
    for (int j = 1; j <= LOG; j++) {
        up[u][j] = up[up[u][j - 1]][j - 1];
    }
    for (int v : g[u]) {
        if (v == fa) continue;
        dfs(v, u);
    }
}

// 查询节点 a 和 b 的最近公共祖先。
int lca(int a, int b) {
    if (depth[a] < depth[b]) swap(a, b);

    // 先把深的点 a 提到与 b 同一深度，距离拆成二进制位依次跳。
    int diff = depth[a] - depth[b];
    for (int j = 0; j <= LOG; j++) {
        if (diff & (1 << j)) a = up[a][j];
    }
    if (a == b) return a;

    // 两个点一起从大到小跳，跳到 LCA 下面一层。
    for (int j = LOG; j >= 0; j--) {
        if (up[a][j] != up[b][j]) {
            a = up[a][j];
            b = up[b][j];
        }
    }
    return up[a][0];
}

// 树上两点 u, v 的距离：depth[u] + depth[v] - 2 * depth[lca(u,v)]。
int dist(int u, int v) {
    int c = lca(u, v);
    return depth[u] + depth[v] - 2 * depth[c];
}

// 判断点 x 是否在路径 u-v 上：用距离拆分等式。
// 树上唯一路径意味着 dist(u,x) + dist(x,v) == dist(u,v) 恰好表示 x 在 u 到 v 的路径上。
bool on_path(int x, int u, int v) {
    return dist(u, x) + dist(x, v) == dist(u, v);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    cin >> n >> q;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    dfs(1, 0);

    while (q--) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;

        // 两条路径各自最高点：lca(a,b) 与 lca(c,d)。
        int p = lca(a, b);
        int r = lca(c, d);

        // 路径 a-b 与 c-d 相交：某一条路径的 LCA 落在另一条路径上。
        if (on_path(p, c, d) || on_path(r, a, b))
            cout << "Y\n";
        else
            cout << "N\n";
    }

    return 0;
}

复杂度

时间：预处理 $O(n \log n)$ ；每次询问至多 8 次 LCA 调用， $O(\log n)$ ，总 $O((n+q) \log n)$ 。
空间：倍增表 $O(n \log n)$ ，邻接表与深度数组 $O(n)$ 。

总结

树上路径相交问题的通用套路是"用 LCA 定位路径、用距离拆分判断点在路径上"：先算出两条路径各自的最高点，再检查对方的最高点是否落在自己的路径上。它把"枚举路径点"降成"常数次 LCA 查询"。rbook 的《倍增求 LCA》讲解了本解使用的 BinaryLCA 模板（lca-binary-lifting）：depth、up、lca、dist 四个部分直接对应代码结构。

图示解析

这张 ASCII 图展示整道题的解题路线：

text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18朴素模拟（brute.cpp）
  标记路径 a->b 的点，再爬路径 c->d 检查碰撞      O(n) 每次询问
        |
        | 瓶颈：枚举路径上的每个点，q 次询问 O(n*q) 太大
        v
关键观察
  路径最高点 = lca(a,b)、lca(c,d)
  两路径相交 <=> 某条路径的 LCA 落在另一条路径上
  点在路径上 <=> dist(u,x) + dist(x,v) == dist(u,v)（距离拆分）
        |
        v
倍增 LCA（main.cpp，模板 lca-binary-lifting）
  dfs 预处理 depth[] 与 up[u][j] = 2^j 级祖先      O(n log n)
  询问：p = lca(a,b)，r = lca(c,d)
  on_path(p, c, d) || on_path(r, a, b)             O(log n) 每次询问
        |
        v
复杂度 O((n + q) log n)，空间 O(n log n)

图中三条主线对应"暴力慢在哪"“相交判定如何只依赖两个 LCA”“距离拆分如何把点在路径上的判断变成常数次 LCA”。核心是把路径这个"点集合"压缩成两个结构性点（LCA），用距离等式验证归属，路径枚举的困难就此消失。

目录

形式化题目

思路

代码

复杂度

总结

图示解析