「一本通 4.4 练习 2」祖孙询问

形式化题目

给定一棵 $n$ 个节点、根为 $r$ 的有根树（输入中 $b=-1$ 的那条记录标记根），以及 $m$ 个询问。每个询问给出节点 $x$ 与 $y$ ，要求判定两者的祖孙关系并逐行输出：

$x$ 是 $y$ 的祖先，输出 $1$ ；
$y$ 是 $x$ 的祖先，输出 $2$ ；
互不为祖先，输出 $0$ 。

以样例的树为例：根是 $234$ ，它挂着 $12 \sim 19$ 八个孩子， $233$ 单独挂在 $19$ 下面。

graph TD
    r234["234（根）"] --- n12["12"]
    r234 --- n13["13"]
    r234 --- n14["14"]
    r234 --- n15["15"]
    r234 --- n16["16"]
    r234 --- n17["17"]
    r234 --- n18["18"]
    r234 --- n19["19"]
    n19 --- n233["233"]

五个询问依次是 $(234,233)$ 、 $(233,12)$ 、 $(233,13)$ 、 $(233,15)$ 、 $(233,19)$ ： $234$ 在根到 $233$ 的唯一路径 $234 \to 19 \to 233$ 上，输出 $1$ ； $233$ 与 $12,13,15$ 互不在对方到根的路径上，输出 $0$ ； $19$ 在 $233$ 到根的路径上，即 $y$ 是 $x$ 的祖先，输出 $2$ 。与题面样例输出 $1,0,0,0,2$ 一致。

正解

思路

朴素做法先暴露瓶颈。 建树求出每个点的父亲后，对每个询问分别从 $x$ 、 $y$ 出发沿父链走向根，看对方是否出现在链上：遇到 $x$ 到 $y$ 的链 → 输出 $1$ ，遇到反方向 → 输出 $2$ ，都走完没遇到 → 输出 $0$ 。链状树深度可达 $n$ ，每个询问最坏 $O(n)$ ，总 $O(nm)$ ，上限下约 $1.6\times10^9$ 次比较，必然超时。注意瓶颈在哪：树只建一次、询问全程只读，却每个询问都重走一遍同样的根链——" $u$ 的祖先集合"在建树完成时就固定了，朴素做法在反复重算它。直接把每个点的祖先集合存下来是 $O(n^2)$ （链状树），需要一个 $O(n)$ 的压缩表示。

DFS 括号序把祖先集合压成一个区间。 对树做一次 DFS，进入节点 $u$ 时给全局时刻 $timer$ 加一并记 $tin[u]=timer$ ，离开 $u$ 时记 $tout[u]=timer$ （时刻只在进入时递增）。DFS 进入 $u$ 之后、离开 $u$ 之前只会访问 $u$ 的子树，所以：

v \text{ 在 } u \text{ 的子树中} \iff tin[u] \leqslant tin[v] \leqslant tout[u].

反方向也成立：不在 $u$ 子树里的点只可能在进入 $u$ 之前（ $tin$ 更小）或离开 $u$ 之后（ $tin$ 更大）才被访问。而 “ $u$ 是 $v$ 的祖先” 与 “ $v$ 在 $u$ 的子树中” 是同一件事，于是祖先判定 = 区间包含，一次整数比较完成。

每个询问问两遍方向。 $tin$ 两两互异， $x$ 盖住 $y$ 与 $y$ 盖住 $x$ 同时成立只能是 $tin[x]=tin[y]$ 即 $x=y$ ，所以 $x\neq y$ 时两个方向互斥：先判 $x$ 是否盖住 $y$ （输出 $1$ ），再判反方向（输出 $2$ ），都不中输出 $0$ 。预处理一次 $O(n)$ ，每询问 $O(1)$ ，总 $O(n+m)$ 。 $x=y$ 是唯一让两个条件同时成立的情形，按“节点是自己的祖先”输出 $1$ ；样例与测试数据均不含 $x=y$ 的询问，该分支只是实现约定。

样例走一遍。 按代码的栈序（孩子后压先走， $19$ 号先访问）得到下面这一种合法括号序，五个询问的判定直接从区间读出：

询问 $(x,y)$	$x$ 的区间 $[tin,tout]$	$y$ 的区间 $[tin,tout]$	包含关系	输出
$(234,233)$	$[1,10]$	$[3,3]$	$tin_{233}=3 \in [1,10]$ ， $x$ 盖住 $y$	$1$
$(233,12)$	$[3,3]$	$[10,10]$	互不包含	$0$
$(233,13)$	$[3,3]$	$[9,9]$	互不包含	$0$
$(233,15)$	$[3,3]$	$[7,7]$	互不包含	$0$
$(233,19)$	$[3,3]$	$[2,3]$	$tin_{233}=3 \in [2,3]$ ， $y$ 盖住 $x$	$2$

根的区间完整盖住整棵树 $[1,10]$ ；每个叶子是单点区间（如 $[3,3]$ 、 $[7,7]$ ），只能盖住自己。要特别看第 5 行： $tin$ 落在对方区间里说明对方是祖先，对应输出 $2$ ——这正是区分 $1$ 与 $2$ 的关键。DFS 用显式栈实现（进入/离开两阶段），链状树深度 $4\times10^4$ 也不会触发 Python 的递归深度限制。

代码

Python 版：

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#!/usr/bin/env python3
# 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-09-30 18:01
# update_at: 2026-09-30 18:01

import sys
from collections import defaultdict


def assign_times(root: int, graph: dict[int, list[int]]) -> tuple[dict[int, int], dict[int, int]]:
    """迭代 DFS 给有根树标括号序：tin[u] 是 u 的进入时刻，tout[u] 是 u 子树中最后的进入时刻。

    栈元素是 (节点, 父节点, 阶段)：父节点 None 表示没有（根）；阶段 0 进入，记时刻后把
    同一节点的离开阶段压回，再压孩子；阶段 1 离开，只收尾。时刻只在进入时递增，且离开时
    孩子必然已全部进入，所以 tout[u] 恰等于 u 子树中的最大 tin——子树被压进一个连续区间。
    """
    tin: dict[int, int] = {}
    tout: dict[int, int] = {}
    timer = 0
    stack: list[tuple[int, int | None, int]] = [(root, None, 0)]
    while stack:
        u, parent, stage = stack.pop()
        if stage == 0:
            timer += 1
            tin[u] = timer
            stack.append((u, parent, 1))                          # 排队等待本子树走完后收尾
            stack += [(v, u, 0) for v in graph[u] if v != parent]  # 父亲不回头
        else:
            tout[u] = timer
    return tin, tout


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)

    graph: dict[int, list[int]] = defaultdict(list)
    root = -1  # 输入保证会遇到 b = -1 的那一行，把根记在这里
    for _ in range(n):
        a, b = next(data), next(data)
        if b == -1:
            root = a
        else:
            graph[a].append(b)
            graph[b].append(a)

    tin, tout = assign_times(root, graph)

    m = next(data)
    out: list[str] = []
    for _ in range(m):
        x, y = next(data), next(data)
        # 祖先的 [tin, tout] 区间完整盖住后代的进入时刻；x ≠ y 时两者不会同时成立
        x_is_ancestor = tin[x] <= tin[y] <= tout[x]
        y_is_ancestor = tin[y] <= tin[x] <= tout[y]
        out.append('1' if x_is_ancestor else '2' if y_is_ancestor else '0')

    print('\n'.join(out))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

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/**
 * 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-05 08:09
 * update_at: 2026-10-05 08:09
 */
#include <cstdio>
#include <vector>
using namespace std;
typedef long long ll;

// 祖孙询问：DFS 括号序把每棵子树压成一段连续区间，
// "u 是 v 的祖先" 等价于 tin[u] <= tin[v] <= tout[u]。

const int MAXX = 40005; // 节点编号不超过 4×10^4，留几个冗余位置

int n;    // 节点个数
int m;    // 询问个数
int root; // 根节点编号（输入中 b = -1 的那条边的 a）

vector<int> g[MAXX]; // g[u] 保存与 u 相邻的节点编号
int tin[MAXX];       // tin[u] = DFS 进入 u 的时刻
int tout[MAXX];      // tout[u] = u 子树中最大的进入时刻
int timer;           // 全局时刻，只在进入节点时递增

// 显式栈模拟 DFS，每个节点入栈两次（进入阶段、离开阶段），最多 2n 个栈元素
int stack_u[2 * MAXX];     // 栈中节点编号
int stack_par[2 * MAXX];   // 栈中节点的父亲，用来避免走回父亲
int stack_stage[2 * MAXX]; // 0 表示进入该节点，1 表示离开该节点
int top;

// 迭代 DFS 标出括号序，避免链状树递归过深
void build_order() {
    top = 0;
    stack_u[top] = root;
    stack_par[top] = -1;
    stack_stage[top] = 0;
    top++;

    while (top > 0) {
        top--;
        int u = stack_u[top];
        int parent = stack_par[top];
        int stage = stack_stage[top];

        if (stage == 0) {
            timer++;
            tin[u] = timer;
            // 先把 u 的离开阶段压回栈底，再压孩子，
            // 这样孩子全部走完后才轮到 u 收尾，tout[u] 就是子树里最大的 tin
            stack_u[top] = u;
            stack_par[top] = parent;
            stack_stage[top] = 1;
            top++;
            for (int i = 0; i < (int)g[u].size(); i++) {
                int v = g[u][i];
                if (v == parent) {
                    continue; // 父亲不回头
                }
                stack_u[top] = v;
                stack_par[top] = u;
                stack_stage[top] = 0;
                top++;
            }
        } else {
            tout[u] = timer;
        }
    }
}

int main() {
    scanf("%d", &n);
    root = 0;
    for (int i = 1; i <= n; i++) {
        int a, b;
        scanf("%d%d", &a, &b);
        if (b == -1) {
            root = a; // 题目保证会出现这样一行
        } else {
            g[a].push_back(b);
            g[b].push_back(a);
        }
    }

    build_order();

    scanf("%d", &m);
    for (int i = 1; i <= m; i++) {
        int x, y;
        scanf("%d%d", &x, &y);
        // x ≠ y 时两个方向的包含关系互斥，先判 x 是否为祖先
        if (tin[x] <= tin[y] && tin[y] <= tout[x]) {
            printf("1\n");
        } else if (tin[y] <= tin[x] && tin[x] <= tout[y]) {
            printf("2\n");
        } else {
            printf("0\n");
        }
    }
    return 0;
}

复杂度

时间复杂度： $O(n+m)$ 。建邻接表 $O(n)$ ，两阶段迭代 DFS 标号每条边检查两次、 $O(n)$ ， $m$ 个询问每个两次整数比较。
空间复杂度： $O(n+m)$ 。邻接表、tin/tout 两张时刻表与显式栈各 $O(n)$ ，输出列表 $O(m)$ ；实测峰值约 41.1 MB，在 128 MB 限制内。

总结

核心观察：DFS 的进入/离开时刻把每个子树压成连续区间，“ $u$ 是 $v$ 的祖先” 等价于 “ $tin[u] \leqslant tin[v] \leqslant tout[u]$ ”，一次比较替代一次走链。
朴素解法 $O(nm)$ 的瓶颈是"每个询问重算固定的祖先集合"，正解用 $O(n)$ 预处理把它压成区间，每询问降到 $O(1)$ ，整体 $O(n+m)$ 与 C++ 正解同阶。
实现要点：DFS 用显式栈的进入/离开两阶段（压回自身的离开阶段后再压孩子，保证配对顺序），tin/tout 用 dict 按原编号存取，兼容编号稀疏；真实数据 10 组全部一致，最大一组 0.059 s、峰值 41.1 MB。

「一本通 4.4 练习 2」祖孙询问

目录

形式化题目

正解

思路

代码

复杂度

总结