[HEOI2016/TJOI2016] 树

形式化题目

给定一棵以 $1$ 为根的有根树，维护一个节点标记集合 $M$ ，初始状态下只有根节点有标记，即 $M = \{1\}$ 。按时间顺序处理以下两类操作：

标记操作 C u：将节点 $u$ 加入集合 $M$ （可重复标记，多次标记效果等同于已存在）；
询问操作 Q u：查询从节点 $u$ 到根的路径上，距离 $u$ 最近（即深度最大）的已标记节点（ $u$ 本身若已标记则为其自身）。

解法总览

本题的核心矛盾在于：正向处理时，每次标记会在原有的树连通结构中增加分割点，将连通块进一步打散；而在询问时，需要沿着祖先链向上寻找第一个进入的标记。

根据是否强制在线，本题有两种经典的处理路线：

离线时光倒流 + 并查集（推荐主解，代码极简）：题目没有强制在线。如果正难则反，记录所有标记后将时间倒流，原问题的「增加标记」就变成了「删除标记」。在并查集中，连通块的合并比分裂容易得多：每个未标记节点直接指向父亲，集合代表元恰好是当前块顶端有标记的祖先；撤销标记时，代表元向其父亲连边合并。单次操作均摊 $O(\alpha(n))$ ，代码仅约 50 行。
在线重链剖分 + 线段树（经典在线解法）：若题目要求强制在线，则用重链剖分将树上到根路径拆分为 $O(\log n)$ 段重链区间，利用线段树维护区间内已标记的最大 dfn 序，沿重链跳跃查询。单次操作复杂度为 $O(\log^2 n)$ 。

下面给出并列解法总览表：

解法	核心观察	复杂度	适用场景	对应代码
解法一（推荐主解）：离线时光倒流 + 并查集	正难则反，删标记等价于连通块向上合并	时间 $O((n+q)\alpha(n))$ ，空间 $O(n)$	题目允许离线；追求实现极简与极致常数	`@include-code(./main.cpp, cpp)`
解法二：重链剖分 + 线段树	祖先路径拆为 $O(\log n)$ 段区间，重链上「最近」即「dfn 最大」	时间 $O(q \log^2 n)$ ，空间 $O(n)$	强制在线或动态加边等扩展场景	`@include-code(./hld.cpp, cpp)`

暴力解法

思路

每次询问 Q u 时，从节点 $u$ 沿树上的唯一父节点链 parent[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;
}

复杂度与瓶颈

时间复杂度：标记单次 $O(1)$ ，询问单次最坏需要向上遍历整条链，最坏时间复杂度为 $O(n)$ ；总时间复杂度为 $O(nq)$ 。
空间复杂度： $O(n)$ 。
瓶颈：当树退化为一条长链且多次在链底发起询问时，逐点上跳产生大量重复扫描。

解法一（推荐主解）：离线时光倒流 + 并查集

思路

正向过程中，不断加入标记会将一棵树割裂成越来越多的「连通块」（以每个标记节点为连通块的顶部代表元）。在数据结构中，分裂通常难以在近线性时间内高效维护，而合并却非常适合并查集。

既然本题全部操作在输入中已经给出，我们采用**时光倒流（逆序处理）**的思想。下面按三块分别讲清，每一块都配一张图。

第一块：离线存操作

正序读入时只存不答：把每个操作原样压进 Operation ops[] 数组，结构体只有三个字段：类型 type、节点号 u、以及留给查询答案的格子 ans。

\operatorname{ops}[i] = (\operatorname{type}_i,\ \operatorname{u}_i,\ \operatorname{ans}_i),\qquad \operatorname{type}_i \in \{\text{'C'},\ \text{'Q'}\},

其中下标 $i$ 就是读入顺序，所以数组天然按时间正序排列，倒序只要让 $i$ 从 $q-1$ 走到 $0$ 。这个数组存在的理由很实际：正序读的时候并不知道答案，但答案属于某条具体的询问，必须先把询问连同它的位置一起存下来，倒序算出答案后再按下标填回去，最后正序扫一遍输出 ans。顺带在读入时做一件事——只有 C 会让标记数变化，所以边读边累加 mark_cnt[u]，读完就得到了「全部操作做完后每个点被标记了几次」。

离线存操作与最终森林的构建: 左上 ops 数组按下标存下每条操作与空的 ans 格, 右上读完后的 mark_cnt 为 1→1 2→1 其余为 0, 下方用最终状态初始化 dsu_fa, 有标记的点自环指向自己, 无标记的点用蓝虚箭头指向父亲, 于是 find(u) 沿指针走到的就是最近的标记祖先

图右下角逐个验证了 find 的结果：find(4) 走 $4 \to 2$ 停在 2，find(3) 走 $3 \to 1$ 停在 1，find(2) 因为自环直接返回 2（这正好对应题面「节点本身也算自己的祖先」）。指针只朝父亲方向指，所以沿指针只会上行，第一个走不动的点就是最近的标记。

第二块：倒序回溯

倒着走一遍操作序列，两种操作的处理方式完全不同：

遇到 Q u：此刻树上的标记状态，恰好就是正序执行到这一步时的状态，直接取代表元 find(u) 记进 ops[i].ans。
遇到 C u：时光倒流意味着这次标记要撤销，所以先 mark_cnt[u]--。只有当它减到 $0$ 时才说明「在更早的时刻 $u$ 其实没有标记」，这时以 $u$ 为根的那一整块才需要向上并进父亲所在的块；否则只减计数，指针一动不动。

第三条是理解这套做法的关键，它解释的是为什么可以只改一个指针、而不用写 merge：撤销 C u 的那一刻， $u$ 自身正带着标记，所以它是所在连通块的代表元（没有任何节点指向它以外的位置），把根 u 挂到 parent[u] 上，效果完全等同于「两块合并」。

倒序回溯: 标记撤销时连通块向上合并: 顶部是倒着走的时间轴, 四个面板依次是从最终状态出发、处理 Q 3 得 1、处理 Q 5 得 2、处理 C 2 时 mark_cnt[2] 归零并把 dsu_fa[2] 从自环改成指向 1, 最后一个宽面板显示回溯完成后 dsu_fa 全部归位, 并对照同一个 Q 2 先后得到 2 和 1

最后那个宽面板值得多看一眼：样例里 Q 2 出现了两次（下标 $0$ 和 $2$ ），倒序处理时它们得到的答案并不相同——先遇到的（ $i=2$ ）时候 2 还带着标记，答案是 2；等走过 C 2、标记被撤销之后，再遇到的（ $i=0$ ）的答案就变成了 1。正序读入时这两条询问长得一模一样，正因为答案取决于「当时的状态」，才必须靠倒序让状态自然回退，而不是真的去维护一个支持删除的结构。

第三块：复杂度

时间复杂度：
- 构建树结构与统计总操作： $O(n + q)$ ；
- 倒序处理中，共计有 $q$ 次查询和最多 $n$ 次并查集合并，带路径压缩的并查集单次均摊为 $O(\alpha(n))$ ；
- 总时间复杂度为 $O((n + q)\alpha(n))$ ，在百万级数据范围内运行只需几十毫秒。
空间复杂度：并查集数组、操作记录均为一维数组，总空间复杂度为 $O(n + q)$ 。

上面两张图都是定格。想把整个过程按代码实际执行的顺序走一遍，可以打开交互动画：存数组 → 倒序扫 → 并查集查询与合并。

页面只有一条时间轴，顶部的箭头就是执行位置，指着哪一格就处理哪一格：

存操作：箭头向右，把每条操作依次填进 ops[]（空格子先留虚线，ans 留问号），同时只有 C 会让 mark_cnt 增长。
建森林：一个点一个点地把 dsu_fa 指出来 —— 有标记指向自己（画成「自」），没标记指向父亲。
倒序扫：箭头转为向左，每退一格处理一条。遇 Q 就在树上画出沿指针上行的路径（带序号），命中的祖先填绿并标「答案 k」，同时把答案写回那一格；遇 C 就撤销标记，若 mark_cnt 归零则用橙色粗箭头把整块挂到父亲上，虚线框标出被合并的整块。
输出：所有 ans 填好后正序扫一遍输出。

每一步都能单步、回退、自动播放；询问步与合并步会先让你猜一下再揭示。页面按题面输入格式读数据，四个预设是题面样例、同一点标两次、深链、多分支，也可以自己粘一组进去，mark_cnt / dsu_fa 两张表随步骤同步高亮。

代码

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-10-23 19:57
 * update_at: 2026-10-23 19:57
 */
// main.cpp：离线时光倒流 + 并查集维护树上连通块与最近标记祖先。
// 复杂度 O((n + q) * alpha(n))，空间 O(n)。
#include <iostream>
#include <vector>

using namespace std;

typedef long long ll;

const int MAXN = 100005;

// parent_node[u] 记录树上节点 u 的父亲节点
int parent_node[MAXN];
// dsu_fa[u] 并查集父节点指针，代表当前连通块中最靠上的已标记节点
int dsu_fa[MAXN];
// mark_cnt[u] 统计节点 u 被标记的总次数
int mark_cnt[MAXN];

// 并查集带路径压缩查询代表元
int find_root(int x) {
    if (dsu_fa[x] == x)
        return x;
    return dsu_fa[x] = find_root(dsu_fa[x]);
}

// 记录操作以便离线处理
struct Operation {
    char type; // 'C' 或 'Q'
    int u;     // 操作节点编号
    int ans;   // 询问操作的答案
};

Operation ops[MAXN];

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

    int n, q;
    std::cin >> n >> q;

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

    // 节点 1 初始已标记，计数值置为 1（且永不降为 0）
    mark_cnt[1] = 1;

    // 离线存询问
    for (int i = 0; i < q; i++) {
        cin >> ops[i].type >> ops[i].u;
        if (ops[i].type == 'C') {
            mark_cnt[ops[i].u]++;
        }
    }

    // 初始化操作结束时的并查集森林：
    // 若点 i 最终被标记（mark_cnt[i] > 0），它自身就是集合的代表元；
    // 若点 i 未被标记，直接将其父指针指向 parent_node[i]。
    for (int i = 1; i <= n; i++) {
        if (mark_cnt[i] > 0) {
            dsu_fa[i] = i;
        } else {
            dsu_fa[i] = parent_node[i];
        }
    }

    // 倒序时光倒流：加标记变成删标记
    for (int i = q - 1; i >= 0; i--) {
        if (ops[i].type == 'Q') {
            ops[i].ans = find_root(ops[i].u);
        } else {
            mark_cnt[ops[i].u]--;
            // 当标记次数归零时，说明在当前操作发生之前，点 ops[i].u 是没有标记的，
            // 它所属集合的代表元 ops[i].u 向父亲所在的集合合并。
            if (mark_cnt[ops[i].u] == 0) {
                dsu_fa[ops[i].u] = parent_node[ops[i].u];
            }
        }
    }

    // 按顺序输出所有询问的答案
    for (int i = 0; i < q; i++) {
        if (ops[i].type == 'Q') {
            cout << ops[i].ans << "\n";
        }
    }

    return 0;
}

解法二：重链剖分 + 线段树

思路

若题目要求在线处理，我们可以将树剖分并将路径查询转化为区间极值：

重链连续性：重链剖分将树上任意节点到根的路径划分为不超过 $O(\log n)$ 段连续的重链区间，重链上深度随剖分后的 dfn 序严格单调递增。
最近与最大 dfn 的等价性：在同一条重链上，离查询点 $u$ 最近的已标记祖先，正是该段重链区间 $[dfn[top[u]], dfn[u]]$ 内所有打了标记的节点中 dfn 最大的节点。
线段树维护：线段树维护单点标记的 dfn，区间查询最大值。询问时沿重链跳跃：若当前重链区间内存在标记，则取区间内最大 dfn 还原为节点编号即为答案；若无标记，则跨过轻边跳至上一条重链继续查询，直到命中。

代码

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;
}

复杂度

时间复杂度：预处理 $O(n)$ ；单次标记为线段树点更新 $O(\log n)$ ；单次询问最多跳 $O(\log n)$ 条链，每条链区间查询 $O(\log n)$ ，单次询问 $O(\log^2 n)$ ；总时间复杂度为 $O(q \log^2 n)$ 。
空间复杂度：线段树及重链剖分相关数组占用 $O(n)$ 空间。

总结

思维模式提升：面对「加标记分割树结构」且不强制在线的题目，「正难则反 / 倒序时光倒流」能将棘手的「分裂问题」转化为经典优雅的「并查集连通块向上合并问题」，从而在代码量和运行效率上双双超越传统高级数据结构。
在线 vs 离线：离线并查集代码极短（50 行），时间近乎线性 $O((n+q)\alpha(n))$ ，是竞赛中最优解题选择；重链剖分 + 线段树则是通用的在线树上路径维护工具，理解两种解法的对立统一有助于加深对树上动态问题的整体认知。

参考与致谢

在解法评估与优化过程中，研读并参考了洛谷公开题解中的精彩解法，特此致谢：

来源与作者	题解标题 / 链接	采纳与参考内容	本文独立完成内容
Sleepp (uid: 77743)	题解 P4092 【[HEOI2016/TJOI2016]树】	学习了将本题离线倒序、利用并查集维护连通块撤销标记的核心思维	严谨证明了代表元直接指向父亲进行路径压缩的拓扑正确性；重写了符合规范的现代 C++17 代码；补充了 500 组随机与极限用例独立对拍验证
现有本地题解作者	本地历史版本	保留了重链剖分 + 线段树的标准在线实现作为并列解法二	补充并列多解法对比表及解法分析，整理格式规范