[HEOI2016/TJOI2016] 树

形式化题目

给定一棵以 1 为根的有根树，维护一个标记集合 $M$ ，初始 $M = \{1\}$ 。支持两类操作：

把节点 $u$ 加入 $M$ （重复加入无效果）；
询问 $u$ 到根路径上深度最大的已标记节点（ $u$ 本身也算自己的祖先）。

要求按顺序处理全部操作，输出每次询问的答案。

思路

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

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/**
 * 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：小数据暴力解，每次查询从节点沿父亲链向上爬，找最近的已标记祖先。
// 复杂度 O(n) 每次操作，只适合小数据，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;

int n, q;
int parent[MAXN];  // parent[u] 记录 u 的父亲（输入是 u -> v 的有向边）
bool marked[MAXN]; // marked[u] 记录 u 是否已被标记

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

    cin >> n >> q;
    // 读入 n-1 条有向边 u -> v，表示 u 是 v 的父亲。
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        parent[v] = u;
    }

    marked[1] = true; // 初始只有根 1 有标记

    while (q--) {
        char opt;
        int u;
        cin >> opt >> u;
        if (opt == 'C') {
            marked[u] = true; // 标记操作：直接置 true（重复标记没有额外效果）
        } else {
            // 询问：从 u 沿父亲链向上爬，第一个被标记的就是最近的标记祖先。
            int cur = u;
            while (!marked[cur])
                cur = parent[cur];
            cout << cur << '\n';
        }
    }

    return 0;
}

brute.cpp 每次询问从 $u$ 沿父亲链向上爬，遇到第一个标记就输出，单次询问最坏 $O(n)$ （链形树），总复杂度 $O(nq)$ ，无法通过 $10^5$ 的数据。

关键观察有两点：

重链剖分把路径拆成 $O(\log n)$ 段：从任意节点到根的路径，按"链头跳链头"的方式只跨 $O(\log n)$ 条轻边，每段是一条重链上的连续 dfn 区间。
同一重链上"最近"就是"dfn 最大"：链上深度随 dfn 严格递增，所以一段链内离 $u$ 最近的已标记节点就是区间内已标记 dfn 最大的那个。

于是用重链剖分 + 线段树：线段树维护每个 dfn 位置的最大已标记 dfn（0 表示无标记）。标记操作是幂等的点更新；询问从 $u$ 出发逐链向上——查 [dfn[top[u]], dfn[u]] 的区间最大值，非 0 就还原成节点输出，否则跳过整段跳到链头的父亲，直到进入包含根的重链（根 1 永远有标记，答案必然存在）。

下面这张 ASCII 图展示样例的查找过程（树形：1-(2,3)、2-(4,5)，重链为 1 -> 2 -> 4，3、5 是轻链）：

text

1
2
3
4
5
6
7
8标记集合变化：
  初始: {1}       -> C 2 后: {1, 2}

Q 2 : 链1 [dfn1,dfn2] 最大已标记 dfn = dfn[2] -> 答案 2
Q 5 : 先查链5 [dfn5,dfn5] 无标记 -> 跳到 parent[5]=2
      再查链1 [dfn1,dfn2] 最大已标记 dfn = dfn[2] -> 答案 2
Q 3 : 先查链3 [dfn3,dfn3] 无标记 -> 跳到 parent[3]=1
      再查根链 [dfn1,dfn1] 最大已标记 dfn = dfn[1] -> 答案 1

观察"Q 5"和"Q 3"的路径：它们都先查了自己的链段（没有标记），各跨一条轻边才到达根所在的重链，这正是"逐链向上"只走 $O(\log n)$ 段的原因；而"Q 2"因为目标就在自己链上，一次区间查询直接命中。

代码

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/**
 * 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：重链剖分 + 线段树维护区间最大 dfn，查询节点到根路径上最近的已标记祖先。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;

int n, q;
vector<int> children[MAXN]; // children[u] 记录 u 的儿子列表（输入是 u -> v 的有向边）
int parent[MAXN];           // parent[u] 记录 u 的父亲
int depth[MAXN];            // depth[u] 记录 u 的深度
int subtree_size[MAXN];     // subtree_size[u] 记录 u 的子树大小
int heavy_son[MAXN];        // heavy_son[u] 记录 u 的重儿子（子树最大的儿子）
int top[MAXN];              // top[u] 记录 u 所在重链的链头
int dfn[MAXN];              // dfn[u] 记录 u 剖分后的新编号
int node_at[MAXN];          // node_at[dfn] 是编号 dfn 对应的原节点

// ---------- 线段树：维护区间内最大的已标记 dfn ----------
int seg_tree[MAXN * 4]; // seg_tree[p] 保存节点 p 区间内最大的已标记 dfn，0 表示该区间没有标记

// 给位置 pos 打标记（标记幂等：重复写同一个 dfn 结果不变）。
void point_mark(int p, int l, int r, int pos) {
    if (l == r) {
        seg_tree[p] = pos;
        return;
    }
    int mid = (l + r) >> 1;
    if (pos <= mid)
        point_mark(p << 1, l, mid, pos);
    else
        point_mark(p << 1 | 1, mid + 1, r, pos);
    seg_tree[p] = max(seg_tree[p << 1], seg_tree[p << 1 | 1]);
}

// 查询区间 [ql, qr] 内最大的已标记 dfn，0 表示区间内没有标记。
int range_max(int p, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr)
        return seg_tree[p];
    int mid = (l + r) >> 1;
    int res = 0;
    if (ql <= mid)
        res = max(res, range_max(p << 1, l, mid, ql, qr));
    if (qr > mid)
        res = max(res, range_max(p << 1 | 1, mid + 1, r, ql, qr));
    return res;
}

// 询问节点 u 到根路径上最近的已标记祖先（u 本身也算祖先）。
int query_marked_ancestor(int u) {
    while (top[u] != 1) {
        // 先看当前链 [top[u], u] 上有没有标记，有则取 dfn 最大的（就是最近的）。
        int got = range_max(1, 1, n, dfn[top[u]], dfn[u]);
        if (got != 0)
            return node_at[got];
        // 当前链没有标记，跨过一条轻边，去上一段重链继续找。
        u = parent[top[u]];
    }
    // u 与根 1 同链：区间 [dfn[1], dfn[u]] 上一定有标记（根 1 永远有标记）。
    return node_at[range_max(1, 1, n, dfn[1], dfn[u])];
}

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

    cin >> n >> q;
    // 读入 n-1 条有向边 u -> v，表示 u 是 v 的父亲。
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        children[u].push_back(v);
    }

    // 从根 1 出发 BFS：确定 parent、depth，并得到从根到叶的访问顺序 order。
    int order[MAXN];
    int order_len = 0;
    int bfs_queue[MAXN];
    int head = 0, tail = 0;
    bfs_queue[tail++] = 1;
    while (head < tail) {
        int u = bfs_queue[head++];
        order[order_len++] = u;
        for (int i = 0; i < (int)children[u].size(); i++) {
            int v = children[u][i];
            parent[v] = u;
            depth[v] = depth[u] + 1;
            bfs_queue[tail++] = v;
        }
    }

    // 逆序遍历 order：累计子树大小，选出每个点的重儿子。
    for (int i = 1; i <= n; i++)
        subtree_size[i] = 1;
    for (int i = n - 1; i >= 1; i--) {
        int u = order[i];
        subtree_size[parent[u]] += subtree_size[u];
        if (subtree_size[u] > subtree_size[heavy_son[parent[u]]])
            heavy_son[parent[u]] = u;
    }

    // 重链剖分编号（栈模拟 DFS）：重儿子优先连续编号，轻儿子开启新链。
    int stk_u[MAXN], stk_t[MAXN]; // 栈：待处理的节点和它的链头
    int stk_len = 0;
    int timer = 0;
    stk_u[++stk_len] = 1;
    stk_t[stk_len] = 1;
    while (stk_len) {
        int u = stk_u[stk_len], t = stk_t[stk_len];
        stk_len--;
        // 沿重儿子一路走到链尾，整条重链的 dfn 连续。
        while (u) {
            top[u] = t;
            dfn[u] = ++timer;
            node_at[timer] = u;
            // 轻儿子是新链的链头，先压栈，之后处理。
            for (int i = 0; i < (int)children[u].size(); i++) {
                int v = children[u][i];
                if (v != heavy_son[u]) {
                    stk_u[++stk_len] = v;
                    stk_t[stk_len] = v;
                }
            }
            u = heavy_son[u];
        }
    }

    // 初始只有根 1 有标记。
    point_mark(1, 1, n, dfn[1]);

    while (q--) {
        char opt;
        int u;
        cin >> opt >> u;
        if (opt == 'C')
            point_mark(1, 1, n, dfn[u]); // 标记：点更新
        else
            cout << query_marked_ancestor(u) << '\n'; // 询问：沿链查询
    }

    return 0;
}

复杂度

预处理：BFS + 子树统计 + 重链编号， $O(n)$ 。
标记 C u：线段树点更新 $O(\log n)$ 。
询问 Q u：最多跨 $O(\log n)$ 条轻边，每段区间 max $O(\log n)$ ，总 $O(\log^2 n)$ 。
空间： $O(n)$ 。

总结

“向上找最近标记祖先"的通用套路：用重链剖分把祖先路径拆成 $O(\log n)$ 段连续区间，把"最近"翻译成"段内最大已标记 dfn”，交给线段树维护。本题标记是单点幂等更新，比常规路径修改题更简单，但"逐链向上 + 链段内贪心"的框架与 rbook 的《树链剖分》文章中的路径操作（hld 模板）完全一致。

图示解析

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

text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18朴素模拟（brute.cpp）
  沿 parent[] 链逐点向上爬，第一个标记即答案     O(n) 每次询问
        |
        | 瓶颈：链形树一次询问 O(n)，q 次操作 O(n*q) 太大
        v
关键观察
  重链剖分：祖先路径拆成 O(log n) 段连续 dfn 区间
  同一条重链上深度随 dfn 递增 -> "最近" = "段内最大已标记 dfn"
  根 1 永远有标记 -> 答案恒存在
        |
        v
重链剖分 + 线段树（main.cpp）
  点标记：线段树点更新 dfn[u]（幂等）
  询问：逐链查 [dfn[top[u]], dfn[u]] 区间最大值
        非 0 用 node_at 还原节点输出；否则跳到链头父亲
        |
        v
复杂度 O(n + q log^2 n)，空间 O(n)

图中四条主线分别对应"暴力慢在哪"“剖分给出什么性质”“正式解如何利用性质”“代价是多少”。核心是把"沿链逐点爬"换成"沿链段跳"，每跳一段用线段树 $O(\log n)$ 回答"这段有没有标记、最近的是谁"。