Qtree3

形式化题目

有一棵 $n$ 个节点的树，根固定为 1，每个节点有黑白两种颜色，初始全为白。给出 $m$ 次操作：

把节点 $i$ 的颜色取反（白变黑、黑变白）；
查询根 1 到节点 $v$ 的路径上深度最小的黑点，输出它的编号；路径上没有黑点输出 $-1$ 。

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

思路

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

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/**
 * 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：小数据暴力解，用来帮助理解题意并辅助对拍。
// 每次查询从 v 沿父链一路爬到根，途中最靠近根的那个黑点就是路径上的第一个黑点。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;

int n, q;
vector<int> g[MAXN]; // 邻接表存树
int parent[MAXN];    // parent[u]：u 的父亲（根 1 的父亲为 0）
bool black[MAXN];    // black[u]：节点 u 当前是否为黑点

// 从根 1 做 BFS，求出每个节点的父亲。
void bfs_parent(int root) {
    queue<int> qu;
    qu.push(root);
    parent[root] = 0;
    while (!qu.empty()) {
        int u = qu.front();
        qu.pop();
        for (int j = 0; j < (int)g[u].size(); j++) {
            int v = g[u][j];
            if (v == parent[u]) continue;
            parent[v] = u;
            qu.push(v);
        }
    }
}

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

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

    bfs_parent(1);

    while (q--) {
        int op, x;
        cin >> op >> x;
        if (op == 0) {
            black[x] = !black[x];
        } else {
            // 沿父链从 x 爬到根，经过的节点正好是根到 x 的整条路径；
            // 遇到黑点就记录，最后一次记录的黑点最靠近根，就是第一个黑点。
            int ans = -1;
            for (int u = x; u != 0; u = parent[u]) {
                if (black[u]) ans = u;
            }
            cout << ans << '\n';
        }
    }

    return 0;
}

brute.cpp 直接维护颜色数组：取反只改一个点；查询从 v 沿父链一路爬到根，途中遇到黑点就记录，最后一次记录的黑点（最靠近根）就是路径上第一个黑点。单次查询 $O(depth)$ ，链形树上一条路径可达 $n$ 个节点，总复杂度 $O(nm)$ ，无法通过 $10^5$ 的数据。

关键观察有两点：

重链内 dfn 与深度同序：同一条重链上从链头到链尾，dfn 严格递增、深度也严格递增，所以"段内最浅的黑点"等价于"段内 dfn 最小的黑点"。
路径拆段后深度严格分层：根到 v 的路径可以拆成 $O(\log n)$ 段重链区间，从根侧到 v 侧逐段排列，前一段的所有节点都比后一段浅。所以按"根侧 → v 侧"的顺序逐段查询区间最小 dfn，第一个非 INF 的 dfn 就是全局最浅黑点。

于是用树链剖分 + 线段树：剖分后每个节点的 dfn 确定，线段树叶子存"该节点是黑点 ? dfn : INF"，内部节点存区间最小 dfn；初始全白，整棵树填 INF，不需要 build。操作 0 是叶子点更新，操作 1 从 v 向上收集重链段（最后一段必含根 1），再逆序遍历逐段查询。

以样例树为例，重儿子优先编号后的 dfn 如下（重链 1-2-9-8-6 被连续编号为 1…5）：

节点	1	2	9	8	6	7	5	4	3
dfn	1	2	3	4	5	6	7	8	9

观察第一行：重链段内 dfn 越大节点越深，所以段内最小 dfn 一定是最浅的黑点。

再按顺序模拟样例的全部操作，段内最小 dfn 与输出的关系如下：

操作	拆出的重链段（根侧 → v）	各段最小 dfn	输出
`1 3`	`[1,1]` → `[9,9]`	INF, INF	-1
`0 8`	8 变黑，叶子写 dfn[8]=4
`1 6`	`[1,5]`	4 → 节点 8	8
`1 7`	`[1,3]` → `[6,6]`	INF, INF	-1
`0 2`	2 变黑，叶子写 dfn[2]=2
`1 9`	`[1,3]`	2 → 节点 2	2
`0 2`	2 变白，叶子写 INF
`1 9`	`[1,3]`	INF	-1

对比 1 6 和 1 7 两行：8 是黑点且 dfn=4，但 1 7 的路径段是 [1,3] 和 [6,6]，dfn=4 不在其中，所以答案仍是 -1；这说明"先拆段、按顺序查段"是必须的，不能直接查全树。1 9 一行则体现了段内最小 dfn = 段内最浅黑点：路径上黑点 2 在段 [1,3] 内且 dfn 最小，直接输出 2。

本解由 rbook 的《树链剖分》文章与模板（hld）改造而来：两次遍历求剖分数组、按重链段处理路径的框架完全一致，差异只在本题线段树维护的是"最小 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
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168/**
 * 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
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;
const int INF = 0x3f3f3f3f;

int n, q;
vector<int> g[MAXN]; // 邻接表存树

// ---------- 树链剖分相关数组（根为 1） ----------
int parent[MAXN];     // parent[u]：u 的父亲
int depth[MAXN];      // depth[u]：u 的深度
int sz[MAXN];         // sz[u]：u 的子树大小
int heavy_son[MAXN];  // heavy_son[u]：u 的重儿子（子树最大的儿子）
int top[MAXN];        // top[u]：u 所在重链的链头
int dfn[MAXN];        // dfn[u]：u 的 DFS 新编号
int node_at[MAXN];    // node_at[dfn]：新编号对应的原节点
int timer;            // DFS 编号计时器

// ---------- 线段树：维护区间内黑点的最小 dfn ----------
int tree[MAXN * 4];   // tree[p]：节点 p 区间内黑点 dfn 的最小值，没有黑点为 INF
bool black[MAXN];     // black[u]：节点 u 当前是否为黑点

// 点更新：把位置 pos 的值改成 value。
void seg_update(int p, int l, int r, int pos, int value) {
    if (l == r) {
        tree[p] = value;
        return;
    }
    int mid = (l + r) >> 1;
    if (pos <= mid)
        seg_update(p << 1, l, mid, pos, value);
    else
        seg_update(p << 1 | 1, mid + 1, r, pos, value);
    tree[p] = min(tree[p << 1], tree[p << 1 | 1]);
}

// 区间查询：返回区间 [ql, qr] 内黑点的最小 dfn，没有黑点返回 INF。
int seg_query(int p, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr)
        return tree[p];
    int mid = (l + r) >> 1;
    int res = INF;
    if (ql <= mid) res = min(res, seg_query(p << 1, l, mid, ql, qr));
    if (qr > mid) res = min(res, seg_query(p << 1 | 1, mid + 1, r, ql, qr));
    return res;
}

// 切换节点 u 的颜色，并更新线段树对应叶子。
void toggle(int u) {
    black[u] = !black[u];
    int value = black[u] ? dfn[u] : INF;
    seg_update(1, 1, n, dfn[u], value);
}

// 查询根 1 到 v 的路径上深度最小的黑点（即第一个黑点），没有则返回 -1。
int query_first_black(int v) {
    vector<pair<int, int>> segments; // 记录路径拆出的重链段，从 v 往根方向收集
    int u = v;
    while (top[u] != 1) {
        segments.push_back(make_pair(dfn[top[u]], dfn[u]));
        u = parent[top[u]];
    }
    segments.push_back(make_pair(dfn[1], dfn[u])); // 最后一段包含根 1

    // 从根侧往 v 方向逐段查询，第一段出现黑点的就是答案所在段。
    // 段内 dfn 最小即深度最小，所以第一个非 INF 的 dfn 就是最浅黑点。
    for (int i = (int)segments.size() - 1; i >= 0; i--) {
        int l = segments[i].first;
        int r = segments[i].second;
        int min_dfn = seg_query(1, 1, n, l, r);
        if (min_dfn != INF)
            return node_at[min_dfn];
    }
    return -1;
}

// 预处理：按 BFS 序求父亲、深度，逆序求子树大小和重儿子。
// 用迭代写法，避免 1e5 深链上递归 DFS 撑爆系统栈。
void preprocess(int root) {
    vector<int> order; // BFS 访问顺序，父节点总在子节点之前
    order.push_back(root);
    depth[root] = 1;
    for (int i = 0; i < (int)order.size(); i++) {
        int u = order[i];
        for (int j = 0; j < (int)g[u].size(); j++) {
            int v = g[u][j];
            if (v == parent[u]) continue; // 跳过父节点
            parent[v] = u;
            depth[v] = depth[u] + 1;
            order.push_back(v);
        }
    }
    // 子树大小：按 BFS 逆序向上累加，顺便找出每个点的重儿子。
    for (int i = (int)order.size() - 1; i >= 0; i--) {
        int u = order[i];
        sz[u] = 1;
        heavy_son[u] = 0;
        for (int j = 0; j < (int)g[u].size(); j++) {
            int v = g[u][j];
            if (v == parent[u]) continue;
            sz[u] += sz[v];
            if (heavy_son[u] == 0 || sz[v] > sz[heavy_son[u]])
                heavy_son[u] = v;
        }
    }
}

// 第二次 DFS：优先走重儿子分配连续 dfn，轻儿子开启新链。
// 用栈模拟递归，保证链头到链尾的 dfn 严格递增。
void decompose(int root) {
    vector<pair<int, int>> st; // (节点, 链头)，先处理根所在重链
    st.push_back(make_pair(root, root));
    while (!st.empty()) {
        pair<int, int> cur = st.back();
        st.pop_back();
        int u = cur.first;
        int chain_top = cur.second;
        while (u != 0) {
            top[u] = chain_top;
            timer++;
            dfn[u] = timer;
            node_at[timer] = u;
            for (int j = 0; j < (int)g[u].size(); j++) {
                int v = g[u][j];
                if (v != parent[u] && v != heavy_son[u])
                    st.push_back(make_pair(v, v)); // 轻儿子开启新链
            }
            u = heavy_son[u]; // 重儿子继续当前链
        }
    }
}

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

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

    preprocess(1);
    decompose(1);

    fill(tree, tree + MAXN * 4, INF); // 初始全白，整棵树没有黑点

    while (q--) {
        int op, x;
        cin >> op >> x;
        if (op == 0)
            toggle(x);
        else
            cout << query_first_black(x) << '\n';
    }

    return 0;
}

复杂度

时间：预处理 $O(n)$ ，单点取反 $O(\log n)$ ，路径查询拆成 $O(\log n)$ 段、每段 $O(\log n)$ ，总 $O((n + m) \log^2 n)$ 。
空间：邻接表、剖分数组与四倍线段树， $O(n)$ 。

总结

“路径上第一个 / 最浅的某种点"是树剖的典型应用：树剖把路径拆成有序的重链段，线段树维护段内"按深度的顺序量”（这里是最小 dfn），从根侧到目标侧逐段查询，第一个命中就是答案。"用 dfn 代替深度"的技巧来自"重链内 dfn 与深度同序"这一条性质，它让区间最小值查询直接给出深度最小的黑点。

图示解析

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

text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18朴素模拟（brute.cpp）
  每个查询从 v 沿父链爬到根，逐个节点看颜色      O(depth) 每次查询
        |
        | 瓶颈：链形树上一条路径可达 n 个节点，m 次查询 O(n*m)
        v
关键观察
  重链内 dfn 与深度同序 → 段内最浅黑点 = 段内最小 dfn
  根到 v 的路径 = 若干重链段，从根侧到 v 侧深度严格分层
        |
        v
树链剖分 + 线段树（main.cpp）
  两次遍历求 parent/depth/sz/heavy_son/top/dfn
  叶子存黑点 dfn 或 INF，节点存区间最小 dfn
  取反：单点更新叶子，O(log n)
  查询：从根侧逐段查区间最小值，第一个非 INF 即答案，O(log^2 n)
        |
        v
复杂度 O((n + m) log^2 n)，空间 O(n)

图中三条主线对应"暴力慢在哪里"“观察把最浅黑点变成了最小 dfn”“正式解如何用段查询替代逐点爬行”。核心是把"路径上按深度找第一个黑点"翻译成"若干有序区间上的最小值查询"：重链内 dfn 与深度同序，段间按深度严格分层，两个性质合起来就保证了"逐段查最小 dfn、第一个命中"的正确性。

目录

形式化题目

思路

代码

复杂度

总结

图示解析