仓鼠找 sugar

形式化题目

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

记 $d(u,v)$ 为树上距离。树上的关键性质是：两点之间的简单路径唯一，且任意两点间的路径是整个树上最短且唯一的一条。

解法总览

这题的核心困难在于：路径是「一堆点」，直接比较需要枚举。四条路线都围绕「怎么把路径压成常数个关键点或一个代数式」展开：

解法	核心观察	复杂度	适用场景	对应代码
一、LCA 判据	相交 $\iff$ 某条路径的 LCA 落在另一条路径上；点在路径上用 $d(u,x)+d(x,v)=d(u,v)$ 判定	$O((n+q)\log n)$	结论最常用、可迁移到路径交等题目，正式主解	`main.cpp` / `main.py`
二、距离和比较	相交 $\iff d(a,b)+d(c,d) \geqslant d(a,c)+d(b,d)$	$O((n+q)\log n)$ ，每次只 4 次 LCA	代码最短、常数最小	`main2.cpp`
三、树链剖分染色	给 $a \to b$ 整条路径 $+1$ ，查 $c \to d$ 上的最大值是否 $>0$ ，再 $-1$ 撤销	$O((n+q)\log^2 n)$	不需要任何结构性结论，纯机械做法	`main3.cpp`
四、枚举路径点	标记 $a \to b$ 上的每个点，再沿 $c \to d$ 爬一遍查碰撞	$O(nq)$	只用于小数据对拍	`brute.cpp`

解法一是正式主解：它的判定条件最简洁，证明只用到「LCA 是路径上离根最近的点」这一条，而且这个套路能直接推广到「求两条路径的交」等变体。解法二是同一件事的代数形式，代码短到几乎不用写函数；解法三则示范了完全不想结论、纯靠数据结构强做的路线。

解法一：LCA 判据 + 距离拆分

思路

先把「路径」这个点集压成一个结构性的点。以任意点为根（这里取 $1$ 号点），路径 $a \to b$ 上离根最近的点就是

p = \operatorname{lca}(a,b)

整条路径等于「 $a$ 爬到 $p$ 」和「 $b$ 爬到 $p$ 」两条链的并，所以 $p$ 是这条路径的「最高点」。同理 $r = \operatorname{lca}(c,d)$ 是路径 $c \to d$ 的最高点。于是有

引理 1（相交判据）：两条路径相交，当且仅当

p \in \text{路径}(c,d) \quad\text{或}\quad r \in \text{路径}(a,b)

证明：

充分性（判据成立 $\Rightarrow$ 两条路径相交）： $p$ 本来就是 $\operatorname{lca}(a,b)$ ，落在路径 $a \to b$ 上（这是 LCA 的定义性质）。所以只要 $p$ 也在路径 $c \to d$ 上，就有一个公共点。 $r$ 的情形完全对称。 $\square$

必要性（两条路径相交 $\Rightarrow$ 判据成立）：设 $x$ 是一个公共点。设 $p,r$ 的深度满足 $d_{\text{root}}(p) \geqslant d_{\text{root}}(r)$ （不满足就把两组端点互换，结论对称）。

路径 $a \to b$ 上所有点都在 $p$ 的子树里，所以 $x$ 是 $p$ 的后代（含 $p$ 本身）；
同理 $x$ 是 $r$ 的后代。

于是 $p$ 与 $r$ 都是 $x$ 的祖先，二者必在同一条到根的链上可比。由 $d_{\text{root}}(p) \geqslant d_{\text{root}}(r)$ 得 $r$ 是 $p$ 的祖先（含相等）。

另一方面， $x$ 在路径 $c \to d$ 上，而这条路径是「 $c$ 爬到 $r$ 」加「 $d$ 爬到 $r$ 」，所以 $x$ 落在 $\text{路径}(r,c)$ 或 $\text{路径}(r,d)$ 上，不妨是前者。此时 $p$ 是 $r$ 的后代、又是 $x$ 的祖先，正好卡在 $r$ 到 $x$ 这一段上：

p \in \text{路径}(r,x) \subseteq \text{路径}(r,c) \subseteq \text{路径}(c,d)

即 $p$ 在路径 $c \to d$ 上，判据成立。 $\square$

注意必要性证明里 $p,r$ 深度相等的情形：此时 $r$ 是 $p$ 的祖先且深度相同，只能 $r = p$ ；而 $r = p = \operatorname{lca}(c,d)$ 当然在路径 $c \to d$ 上，同样成立。

剩下的问题就是「判断点 $x$ 是否在路径 $u \to v$ 上」。用距离拆分：

引理 2： $x$ 在路径 $u \to v$ 上 $\iff d(u,x) + d(x,v) = d(u,v)$ 。

两个方向的含义：充分性指“右端（距离等式）成立就足以断定左端（点在路径上）”，必要性指“左端成立时右端必然成立”。

证明：

充分性（距离等式成立 $\Rightarrow$ 点在路径上）：设等式 $d(u,x) + d(x,v) = d(u,v)$ 成立，要证 $x$ 一定在路径 $u \to v$ 上。用逆否命题，反设 $x$ 不在路径上。树上 $u \to v$ 的路径唯一，取这条路径上离 $x$ 最近的点 $y$ ，则 $y \neq x$ ，且 $x$ 到 $u$ 、 $x$ 到 $v$ 的路都必须先经过 $y$ ，所以

d(u,x) = d(u,y) + d(y,x), \qquad d(x,v) = d(x,y) + d(y,v)

又因 $y$ 落在路径 $u \to v$ 上， $u \to y$ 与 $y \to v$ 首尾相接正好拼成整条 $u \to v$ ，所以它们长度相加就是全长 $d(u,v)$ 。代入得

d(u,x) + d(x,v) = d(u,v) + 2\,d(x,y) > d(u,v)

严格大于，与等式成立矛盾。所以等式成立时 $x$ 必在路径 $u \to v$ 上。

必要性（点在路径上 $\Rightarrow$ 距离等式成立）：设 $x$ 在路径 $u \to v$ 上。路径唯一， $x$ 把它切成 $u \to x$ 与 $x \to v$ 两段，两段首尾相接、长度相加就是全长，故

d(u,x) + d(x,v) = d(u,v)

两个方向合起来即得等价关系。 $\square$

而 $d(u,v) = \text{dep}[u] + \text{dep}[v] - 2\,\text{dep}[\operatorname{lca}(u,v)]$ ，所以一次距离计算就是一次 LCA。每次询问：2 次 LCA 求 $p, r$ ，再用 3 次距离（ $=3$ 次 LCA）判 $p$ ，3 次判 $r$ ，共 8 次 LCA。

样例推演

样例的树（以 $1$ 为根， $2$ 是 $4$ 的儿子， $5$ 是 $2$ 的儿子）：

text

询问	路径 $a \to b$	路径 $c \to d$	$p$	$r$	输出
`2 2 1 4`	$\{2\}$	$\{1,4\}$	$2$	$1$	N
`4 1 3 4`	$\{4,1\}$	$\{3,1,4\}$	$1$	$1$	Y
`3 1 1 5`	$\{3,1\}$	$\{1,4,2,5\}$	$1$	$1$	Y

第二行两个 LCA 都是 $1$ ，而 $1$ 在两条路径上都有，于是相交；第一行 $p=2$ 不在 $\{1,4\}$ 上、 $r=1$ 不在 $\{2\}$ 上，两个方向都失败，于是不相交。注意第一行 $p=2$ 与 $r=1$ 恰好在同一条链上（ $1$ 是 $2$ 的祖先），这正是必要条件证明里「 $r$ 是 $p$ 的祖先」那种情形，但还要 $p$ 落在 $c \to d$ 上才算相交——这也说明两个条件缺一不可。

代码

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/**
 * 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-10-26 16:36
 */
// P3398 仓鼠找 sugar
// 判两条树上路径 a-b 与 c-d 是否有公共点。
// 结论：相交 <=> lca(a,b) 在路径 c-d 上，或 lca(c,d) 在路径 a-b 上。
// 判点在路径上用距离拆分：x 在 u-v 上 <=> dist(u,x) + dist(x,v) == dist(u,v)。
#include <bits/stdc++.h>
using namespace std;

const int maxn = 100000 + 5; // 节点数上限
const int LOG = 17;          // 2^17 = 131072 > 1e5，够跳任意深度差

typedef long long ll;

ll n;              // 节点数
ll q;              // 询问数
vector<int> g[maxn]; // g[u]：与 u 相邻的所有点
ll depth[maxn]; // depth[u]：u 到根（1 号点）的边数
int up[maxn][LOG + 1]; // up[u][j]：u 的 2^j 级祖先，越界时为 0

// 预处理深度与倍增表。
void dfs_build(int u, int fa) {
    depth[u] = depth[fa] + 1;
    up[u][0] = fa;
    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_build(v, u);
    }
}

// 倍增求 LCA，O(log n)。
int lca(int a, int b) {
    if (depth[a] < depth[b]) swap(a, b); // 让 a 是更深的那个

    // 第一步：把 a 提到与 b 同深度，按深度差的二进制位跳。
    ll 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; // b 本来就是 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];
}

// 树上两点距离：按 LCA 拆成两段深度差。
ll dist(int u, int v) {
    int c = lca(u, v);
    return depth[u] + depth[v] - 2 * depth[c];
}

// 判断点 x 是否在路径 u-v 上。
// 树上 u 到 v 只有一条路径，x 不在上面时 dist(u,x)+dist(x,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);

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

    depth[0] = 0; // 0 号点是虚拟根，深度当 0，方便倍增越界
    dfs_build(1, 0);

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

        int p = lca(a, b); // 路径 a-b 上离根最近的点
        int r = lca(c, d); // 路径 c-d 上离根最近的点

        // 两条路径相交 <=> 某一方的「最高点」落在对方路径上。
        if (on_path(p, c, d) || on_path(r, a, b)) {
            cout << "Y\n";
        } else {
            cout << "N\n";
        }
    }

    return 0;
}

python

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
83import sys
from array import array


input = sys.stdin.buffer.readline
n, queries = map(int, input().split())
graph = [[] for _ in range(n + 1)]
for _ in range(n - 1):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)

parent = array("i", [0]) * (n + 1)
depth = array("i", [0]) * (n + 1)
entry = array("i", [0]) * (n + 1)
leave = array("i", [0]) * (n + 1)
order = array("i", [1])
depth[1] = 1
for node in order:
    for neighbor in graph[node]:
        if neighbor != parent[node]:
            parent[neighbor] = node
            depth[neighbor] = depth[node] + 1
            order.append(neighbor)

# Build a real DFS preorder; unlike the parent-building BFS order, it makes
# every subtree a contiguous interval.
subtree = array("i", [1]) * (n + 1)
for node in reversed(order[1:]):
    subtree[parent[node]] += subtree[node]
preorder = []
stack = [1]
while stack:
    node = stack.pop()
    preorder.append(node)
    for neighbor in reversed(graph[node]):
        if neighbor != parent[node]:
            stack.append(neighbor)
for index, node in enumerate(preorder, 1):
    entry[node] = index
    leave[node] = index + subtree[node] - 1

ancestors = [parent]
for _ in range(1, n.bit_length()):
    previous = ancestors[-1]
    ancestors.append(array("i", (previous[previous[node]] for node in range(n + 1))))


def lca(x, y):
    if depth[x] < depth[y]:
        x, y = y, x
    difference = depth[x] - depth[y]
    bit = 0
    while difference:
        if difference & 1:
            x = ancestors[bit][x]
        difference >>= 1
        bit += 1
    if x == y:
        return x
    for level in range(len(ancestors) - 1, -1, -1):
        if ancestors[level][x] != ancestors[level][y]:
            x = ancestors[level][x]
            y = ancestors[level][y]
    return parent[x]


def is_ancestor(x, y):
    return entry[x] <= entry[y] <= leave[x]


def on_path(node, x, y, ancestor):
    return is_ancestor(ancestor, node) and (is_ancestor(node, x) or is_ancestor(node, y))


answers = []
for _ in range(queries):
    a, b, c, d = map(int, input().split())
    ab, cd = lca(a, b), lca(c, d)
    candidates = (ab, cd, lca(a, c), lca(a, d), lca(b, c), lca(b, d))
    meet = any(on_path(node, a, b, ab) and on_path(node, c, d, cd) for node in candidates)
    answers.append('Y' if meet else 'N')
print("\n".join(answers))

复杂度

预处理一次 DFS 建倍增表 $O(n \log n)$ ；每次询问 8 次 LCA， $O(\log n)$ 。总时间 $O((n + q)\log n)$ ，空间 $O(n \log n)$ 。

解法二：距离和比较

思路

换一个完全不同的角度：不解剖路径，直接比较两组「端点配对」的距离和。

引理 3（距离和判据）：路径 $a \to b$ 与 $c \to d$ 相交，当且仅当

d(a,b) + d(c,d) \geqslant d(a,c) + d(b,d)

证明：

先证「相交 $\Rightarrow$ 不等式成立」。设 $x$ 是公共点，则 $x$ 同时落在两条路径上，于是

d(a,b) = d(a,x) + d(x,b), \qquad d(c,d) = d(c,x) + d(x,d)

（ $x$ 在两段路径上，各被切成两半。）另一方面对 $a \to c$ 与 $b \to d$ 用三角不等式：

d(a,c) \leqslant d(a,x) + d(x,c), \qquad d(b,d) \leqslant d(b,x) + d(x,d)

两式相加，右边恰好等于前面两式之和：

d(a,c) + d(b,d) \leqslant \bigl(d(a,x) + d(x,b)\bigr) + \bigl(d(c,x) + d(x,d)\bigr) = d(a,b) + d(c,d)

再证「不相交 $\Rightarrow$ 不等式严格反号」。设两条路径不交，则存在唯一一条最短的「空隙路径」连接它们：设 $u \in \text{路径}(a,b)$ 与 $v \in \text{路径}(c,d)$ 使 $d(u,v) = L$ 最小，则 $L \geqslant 1$ ，且 $u,v$ 之间那段路（除端点外）既不在第一条路径上也不在第二条路径上。

关键点在于：从 $a$ 或 $b$ 走到 $c$ 或 $d$ ，任何一条路都必须穿过这条空隙，且两端都只能接到 $u$ 、 $v$ ：

d(a,c) = d(a,u) + L + d(v,c), \qquad d(b,d) = d(b,u) + L + d(v,d)

另一方面 $u$ 在路径 $a \to b$ 上，所以 $d(a,b) = d(a,u) + d(b,u)$ ； $v$ 在路径 $c \to d$ 上，所以 $d(c,d) = d(c,v) + d(v,d)$ 。两式相加：

d(a,b) + d(c,d) = \bigl(d(a,u)+d(b,u)\bigr) + \bigl(d(v,c)+d(v,d)\bigr)

与前面的 $d(a,c)+d(b,d) = \bigl(d(a,u)+d(b,u)\bigr) + 2L + \bigl(d(v,c)+d(v,d)\bigr)$ 相减，得

d(a,c) + d(b,d) = d(a,b) + d(c,d) + 2L > d(a,b) + d(c,d)

严格反号成立。 $\square$

同样的论证对另一组配对 $(a,d),(b,c)$ 逐字成立，所以两个不等式都能判定答案；代码里任选一个即可。

这个判法的好处是每次询问只要 4 次 LCA（4 个距离），比解法一的 8 次少一半，而且完全不需要「点在路径上」这样的辅助函数。

代码

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/**
 * 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-10-24 14:05
 * update_at: 2026-10-26 16:36
 */
// P3398 仓鼠找 sugar
// 解法二：只比较两次「路径长度 + 交叉距离」，全程 4 次 LCA，代码最短。
// 结论：a-b 与 c-d 相交 <=> dist(a,b) + dist(c,d) >= dist(a,c) + dist(b,d)。
#include <bits/stdc++.h>
using namespace std;

const int maxn = 100000 + 5; // 节点数上限
const int LOG = 17;          // 2^17 = 131072 > 1e5

typedef long long ll;

ll n;                  // 节点数
ll q;                  // 询问数
vector<int> g[maxn];   // g[u]：与 u 相邻的所有点
ll depth[maxn];   // depth[u]：u 到根（1 号点）的边数
int up[maxn][LOG + 1]; // up[u][j]：u 的 2^j 级祖先，越界时为 0

// 预处理深度与倍增表。
void dfs_build(int u, int fa) {
    depth[u] = depth[fa] + 1;
    up[u][0] = fa;
    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_build(v, u);
    }
}

// 倍增求 LCA，O(log n)。
int lca(int a, int b) {
    if (depth[a] < depth[b]) swap(a, b);
    ll 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;
    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];
}

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

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

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

    depth[0] = 0;
    dfs_build(1, 0);

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

        // 同一个端点配对（a-b、c-d）的距离和，不小于交叉配对（a-c、b-d）的距离和
        // 就说明两条路径有公共点。证明见题解。
        ll same_side = dist(a, b) + dist(c, d);
        ll cross_side = dist(a, c) + dist(b, d);

        if (same_side >= cross_side) {
            cout << "Y\n";
        } else {
            cout << "N\n";
        }
    }

    return 0;
}

复杂度

预处理 $O(n \log n)$ ；每次询问 4 次 LCA， $O(\log n)$ 。总时间 $O((n+q)\log n)$ ，空间 $O(n\log n)$ ，常数是三份正解里最小的。

解法三：树链剖分染色

思路

前两种解法都要先想出一条几何结论。这一节反过来：完全不做几何推理，把「相交」直接翻译成数据结构能回答的问题。

思路来自暴力解法四：暴力是「把 $a \to b$ 上的点都打上标记，再看 $c \to d$ 上有没有被标记的点」。唯一的缺点是「沿路径逐个打标记」太慢。但只要能把路径拆成 $O(\log n)$ 段连续区间，就可以用线段树整体处理：

用树链剖分把路径 $a \to b$ 拆成 $O(\log n)$ 条重链上的区间，对每段做区间 $+1$ ；
查询路径 $c \to d$ 上所有位置的最大值，若 $> 0$ 说明有被染色的点；
把刚才那些区间再 $-1$ ，撤销本次染色，保证每次询问互不影响。

把「标记」换成「 $+1$ 」而不是直接置为 $1$ ，正是为了第 3 步能干净地撤销：整个过程中每个位置的值只在 $\{0,1\}$ 之间，区间最大值也就只会是 $0$ 或 $1$ 。

树链剖分的两次 DFS 各负责一件事：第一次求子树大小与重儿子，第二次沿重儿子优先分配剖分序，使每条重链对应一段连续下标。之后「路径上的区间」就变成普通的数组区间，线段树只需支持区间加与区间最大值。

这条路线的教学价值在于：它把「想出结论」这一步整体删掉了，代价是代码变长、复杂度多一个 $\log$ 。对于「两条路径是否相交」这种结论难想的题，这是一条稳妥的保底路线。

代码

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
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159/**
 * 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-10-24 14:05
 * update_at: 2026-10-26 16:36
 */
// P3398 仓鼠找 sugar
// 解法三：不求任何结构性结论，直接做「路径染色 + 查询是否有染色点」。
// 树链剖分把路径拆成 O(log n) 段连续区间，线段树维护区间最大值：
// 给 a-b 整条路径 +1，再查 c-d 上的最大值，非 0 即有公共点，最后把 a-b 的 +1 撤掉。
#include <bits/stdc++.h>
using namespace std;

const int maxn = 100000 + 5; // 节点数上限

typedef long long ll;

ll n;                // 节点数
ll q;                // 询问数
vector<int> g[maxn]; // g[u]：与 u 相邻的所有点
ll parent[maxn];   // parent[u]：u 的父亲
ll depth[maxn];    // depth[u]：u 的深度（根为 1）
ll subtree_size[maxn]; // subtree_size[u]：u 的子树大小
ll heavy_son[maxn];   // heavy_son[u]：u 的重儿子，叶子为 0
ll chain_top[maxn];   // chain_top[u]：u 所在重链的链顶
ll dfn[maxn];         // dfn[u]：u 在剖分序里的位置
ll dfn_cnt;           // 已经分配的剖分序个数

// 线段树：区间加、区间最大值。染色用「加一」，撤销用「减一」。
ll tag[maxn << 2];      // tag[p]：节点 p 的区间加懒标记
ll max_val[maxn << 2];  // max_val[p]：节点 p 对应区间的最大值

// 建树，初始全 0。
void build(int p, int l, int r) {
    tag[p] = 0;
    max_val[p] = 0;
    if (l == r) return;
    int mid = (l + r) >> 1;
    build(p << 1, l, mid);
    build(p << 1 | 1, mid + 1, r);
}

// 把懒标记下发给两个儿子。
void push_down(int p) {
    if (tag[p] == 0) return;
    int v = tag[p];
    tag[p << 1] += v;
    max_val[p << 1] += v;
    tag[p << 1 | 1] += v;
    max_val[p << 1 | 1] += v;
    tag[p] = 0;
}

// 区间 [ql, qr] 整体加 val。
void update(int p, int l, int r, int ql, int qr, int val) {
    if (ql <= l && r <= qr) {
        tag[p] += val;
        max_val[p] += val;
        return;
    }
    push_down(p);
    int mid = (l + r) >> 1;
    if (ql <= mid) update(p << 1, l, mid, ql, qr, val);
    if (qr > mid) update(p << 1 | 1, mid + 1, r, ql, qr, val);
    max_val[p] = max(max_val[p << 1], max_val[p << 1 | 1]);
}

// 查询区间 [ql, qr] 的最大值。
int query_max(int p, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) return max_val[p];
    push_down(p);
    int mid = (l + r) >> 1;
    int res = 0;
    if (ql <= mid) res = max(res, query_max(p << 1, l, mid, ql, qr));
    if (qr > mid) res = max(res, query_max(p << 1 | 1, mid + 1, r, ql, qr));
    return res;
}

// 第一次 DFS：求父亲、深度、子树大小、重儿子。
void dfs_size(int u, int fa) {
    parent[u] = fa;
    depth[u] = depth[fa] + 1;
    subtree_size[u] = 1;
    heavy_son[u] = 0;
    for (int v : g[u]) {
        if (v == fa) continue;
        dfs_size(v, u);
        subtree_size[u] += subtree_size[v];
        if (subtree_size[v] > subtree_size[heavy_son[u]]) heavy_son[u] = v;
    }
}

// 第二次 DFS：沿重儿子优先分配剖分序，保证每条重链是一段连续下标。
void dfs_split(int u, int top) {
    chain_top[u] = top;
    dfn[u] = ++dfn_cnt;
    if (heavy_son[u] != 0) dfs_split(heavy_son[u], top); // 重儿子沿用链顶
    for (int v : g[u]) {
        if (v == parent[u] || v == heavy_son[u]) continue;
        dfs_split(v, v); // 轻儿子自己开一条新链
    }
}

// 给 u-v 路径上所有点的位置加 val，拆成若干条重链上的连续区间。
void path_update(int u, int v, int val) {
    while (chain_top[u] != chain_top[v]) {
        if (depth[chain_top[u]] < depth[chain_top[v]]) swap(u, v);
        update(1, 1, n, dfn[chain_top[u]], dfn[u], val);
        u = parent[chain_top[u]];
    }
    if (depth[u] > depth[v]) swap(u, v);
    update(1, 1, n, dfn[u], dfn[v], val);
}

// 查询 u-v 路径上的最大值，拆法同上。
int path_query(int u, int v) {
    int res = 0;
    while (chain_top[u] != chain_top[v]) {
        if (depth[chain_top[u]] < depth[chain_top[v]]) swap(u, v);
        res = max(res, query_max(1, 1, n, dfn[chain_top[u]], dfn[u]));
        u = parent[chain_top[u]];
    }
    if (depth[u] > depth[v]) swap(u, v);
    res = max(res, query_max(1, 1, n, dfn[u], dfn[v]));
    return res;
}

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

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

    dfs_size(1, 0);
    dfs_split(1, 1);
    build(1, 1, n);

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

        path_update(a, b, 1);              // 把 a-b 整条路径染上色
        if (path_query(c, d) > 0) {        // c-d 上存在染色点即有公共点
            cout << "Y\n";
        } else {
            cout << "N\n";
        }
        path_update(a, b, -1);             // 撤销染色，下一次询问互不影响
    }

    return 0;
}

复杂度

预处理两次 DFS + 建树 $O(n)$ 。每次询问对两条路径各做一次剖分，路径被拆成 $O(\log n)$ 段，每段线段树操作 $O(\log n)$ ，故单次询问 $O(\log^2 n)$ ，总时间 $O(n + q\log^2 n)$ 。

解法四：枚举路径点（对拍用）

思路

完全按定义来。先用 BFS 求出每个点的父亲与深度，然后：

从 $a$ 、 $b$ 两端同时向上爬（深的先单独爬，同深后一起爬），把路径 $a \to b$ 上的每个点标记为已访问；
再从 $c$ 、 $d$ 两端同样地爬，沿途只要碰到被标记的点就说明相交。

两条路径都是靠「端点向上爬」逐点走出来的，单次询问代价是两条路径的长度，最坏 $O(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
109
110/**
 * 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-10-26 16:36
 */
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
// 每次询问先求出树上的父关系与深度，再：
//   1) 从 a 爬到 b，把路径 a-b 上的所有点标记为 1；
//   2) 从 c 爬到 d，沿途检查是否遇到被标记过的点。
// 每条路径用「两个端点同时向上爬」实现，复杂度 O(路径长度)，只适合小数据。
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 105;

ll n, q;
vector<int> g[MAXN]; // 树的邻接表
ll parent[MAXN];     // parent[u] 表示 u 的父节点（根 1 的父节点是 0）
ll 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;
}

复杂度

$O(n)$ 预处理；每次询问 $O(n)$ 。总时间 $O(nq)$ ，只适合 $n, q \leqslant 200$ 的小数据。

复杂度对比

解法	预处理	单次询问	空间	备注
一、LCA 判据	$O(n\log n)$	8 次 LCA	$O(n\log n)$	结论可迁移，主解
二、距离和比较	$O(n\log n)$	4 次 LCA	$O(n\log n)$	常数最小
三、树链剖分染色	$O(n)$	$O(\log^2 n)$	$O(n)$	不需要几何结论
四、枚举路径点	$O(n)$	$O(n)$	$O(n)$	仅对拍

本题 $n, q \leqslant 10^5$ ，题面特别提示了常数问题。三份正解在 $n = q = 10^5$ 的三类树上实测：

代码	链形树	深随机树	一般随机树
`main.cpp`	64 ms	151 ms	196 ms
`main2.cpp`	63 ms	159 ms	148 ms
`main3.cpp`	57 ms	152 ms	246 ms

三者都在 $250$ ms 内，相对 $1$ s 时限留有余量。若时限更紧，解法二（每次只 4 次 LCA）最稳；解法三的 $\log^2$ 常数在一般随机树上最明显。

总结

「两条树上路径是否相交」看起来是个关于点集的问题，但树的结构让它可以塌缩成常数次查询。三种做法对应三种压缩方式：

压成关键点：路径的最高点就是它的 LCA。相交时某个 LCA 必然落到对方路径上（引理 1），于是只比两个点。
压成代数式：相交时公共点把两条路径各自切两半，三角不等式立刻给出 $d(a,b)+d(c,d) \geqslant d(a,c)+d(b,d)$ ；不相交时中间那段空隙会在这个不等式上留下 $2L$ 的缺口（引理 3）。
压成区间：不想几何就上树链剖分，把「沿路径打标记」变成「区间加、区间取最大」，用 $O(\log^2 n)$ 换取「不需要任何结论」。

三者都要用到的共同工具是倍增 LCA：无论是求路径最高点、算两点距离，还是剖分路径，都需要 $O(\log n)$ 的祖先查询。这也是这题被归到 LCA 模板题的原因——真正的难点在判定条件，LCA 只是执行手段。

参考与致谢

下列洛谷公开题解提供了本文的解法来源与对照；本文未复用其原文或代码，题面建模、引理证明、代码与验证均由本文独立完成。

作者与题解	来自原题解	本文独立补充
zhyh (uid 9315)，题解 P3398	「相交则某条路径的 LCA 在另一条路径上」这一判据，以及用「到两端距离和等于路径长」判点在路径上的做法；该文明确指出此前题解多未给证明	补齐定理 1 必要性的完整归纳论证（按两个 LCA 的深度关系分情形），并补引理 2 的严格反证
沧澜 (uid 21719)，题解 P3398	用 `deep[x] >= deep[LCA(s,t)]` 加「 $x$ 是 $s$ 或 $t$ 的祖先」来判点在路径上，走树剖 LCA 的实现路线	指出该祖先式判定与距离拆分等价，并在主解中统一采用距离形式以便复用 `dist`
凉城無愛 (uid 104696)，题解 P3398	从「回头点」直觉出发，取交叉四组 LCA 深度最大值与两条路径 LCA 深度比较的判法	核验其判法与前两种判据等价，但指出它每次需 6 次 LCA，不如距离和判据省；本文未采用
Mathison (uid 74896)，题解 P3398	只用距离和比较、每次 4 次 LCA 的极简判法（原作者的证明只给了直观感觉）	给出引理 3 的完整双向证明：相交用三角不等式，不相交用空隙路径的 $2L$ 缺口
一扶苏一 (uid 65363)，题解 P3398	「路径染色 + 链上查询最大值 + 事后撤销」的树链剖分路线	整理成「区间加而非区间赋值」的写法使撤销自然成立，并说明该路线相对几何判据的取舍
ZORO (uid 127018)，题解 P3398	用「公共点必在某条链的爬升段上、另一条链的 LCA 落在此段祖先链中」的图示解释	把该直观图解释改写为可逐步检验的归纳论证，作为引理 1 的必要性证明

目录