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

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/**
 * 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 20:05
 * update_at: 2026-10-23 21:40
 */
// main.cpp：双 dfs 序 + 线段树二分，O((n+q) log n)（本题目解主解，解法一）。
// 关键性质：u 是 v 的祖先 <=> dfn[u] <= dfn[v] 且 rdfn[u] <= rdfn[v]，
// 其中 dfn 是先序进入时间，rdfn 是把儿子列表翻转后再 DFS 的进入时间。
#include <bits/stdc++.h>
using namespace std;

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

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

int dfn[MAXN];      // dfn[u]：先序 DFS 的进入时间
int rdfn[MAXN];     // rdfn[u]：把每个节点的儿子列表翻转后再 DFS 的进入时间
int node_at[MAXN];  // node_at[i]：dfn 为 i 的节点
int timer;          // 先序编号计数器，从 1 递增到 n
int reverse_timer;  // 退出编号计数器，从 n 递减到 1

bool black[MAXN];   // black[u]：节点 u 当前是否为黑点
int tree[MAXN * 4]; // tree[p]：该区间内黑点 rdfn 的最小值，INF 表示区间内没有黑点

// 一遍 DFS 同时求两个序：进入时 dfn 正向编号，退出时 rdfn 倒着编号。
// rdfn 倒着编号的依据：翻转儿子列表的 DFS 的进入序，正是原 DFS 退出序的逆序。
void dfs(int u, int fa) {
    dfn[u] = ++timer;
    node_at[timer] = u;
    for (int v : g[u])
        if (v != fa) dfs(v, u);
    rdfn[u] = reverse_timer--;
}

// 点更新：把位置 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]);
}

// 在线段树上找最小的下标 i 使叶子值 <= limit（线段树二分），不存在返回 0。
int find_first(int p, int l, int r, int limit) {
    if (tree[p] > limit) return 0; // 整个区间的最小值都超限，区间内没有答案
    if (l == r) return l;
    int mid = (l + r) >> 1;
    if (tree[p << 1] <= limit) return find_first(p << 1, l, mid, limit); // 左半边有答案就进左半边
    return find_first(p << 1 | 1, mid + 1, r, limit);
}

// 查询根 1 到 v 的路径上最浅的黑点编号，没有则返回 -1。
int query_first_black(int v) {
    int pos = find_first(1, 1, n, rdfn[v]); // 最小的 dfn，其节点 rdfn 不超过 rdfn[v]
    if (pos == 0 || pos > dfn[v]) return -1; // 不在 dfn[v] 左侧，说明路径上没有黑点
    return node_at[pos];
}

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

    timer = 0;
    reverse_timer = n;
    dfs(1, 0);

    fill(tree, tree + 4 * n + 4, INF); // 初始全白，所有叶子的值都是 INF

    while (q--) {
        int op, x;
        cin >> op >> x;
        if (op == 0) {
            black[x] = !black[x];
            seg_update(1, 1, n, dfn[x], black[x] ? rdfn[x] : INF);
        } else {
            cout << query_first_black(x) << '\n';
        }
    }

    return 0;
}

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/**
 * 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 21:30
 * update_at: 2026-10-23 21:40
 */
// hld_set.cpp：重链剖分 + 每条重链一个 set（解法二）。
// 每条重链内部 dfn 随深度递增，所以 set 的最小元素就是该链最浅的黑点。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;

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

int parent[MAXN];    // parent[u]：u 的父亲（根的父亲为 0）
int depth[MAXN];     // depth[u]：u 的深度（根为 1）
int sz[MAXN];        // sz[u]：u 的子树大小
int heavy_son[MAXN]; // heavy_son[u]：u 的重儿子，0 表示没有儿子
int top[MAXN];       // top[u]：u 所在重链的链头
int dfn[MAXN];       // dfn[u]：u 剖分后的编号（同一条重链上随深度递增）
int node_at[MAXN];   // node_at[i]：编号 i 对应的原节点
int timer;           // 剖分编号计数器

bool black[MAXN];            // black[u]：节点 u 当前是否为黑点
set<int> chain_black[MAXN];  // chain_black[t]：链头为 t 的重链上所有黑点的 dfn，按 dfn 升序

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

// 第二遍 DFS：先给重儿子编号，让同一条重链的 dfn 连续且随深度递增；轻儿子各自开新链。
void dfs_decompose(int u, int chain_top) {
    top[u] = chain_top;
    dfn[u] = ++timer;
    node_at[timer] = u;
    if (heavy_son[u] != 0) dfs_decompose(heavy_son[u], chain_top);
    for (int v : g[u]) {
        if (v == parent[u] || v == heavy_son[u]) continue;
        dfs_decompose(v, v);
    }
}

// 查询根 1 到 v 的路径上最浅的黑点编号，没有则返回 -1。
// 从 v 所在重链开始向上逐链跳：链上最浅的黑点是 set 的最小 dfn，
// 若它比 dfn[v] 深就说明这条链上没有 v 的祖先被染黑，直接跳过整条链。
int query_first_black(int v) {
    int answer = -1;
    int u = v;
    while (u != 0) {
        int chain_top = top[u];
        if (!chain_black[chain_top].empty()) {
            int shallowest = *chain_black[chain_top].begin();
            if (shallowest <= dfn[u]) answer = node_at[shallowest]; // 越往上跳覆盖的答案越浅
        }
        u = parent[chain_top];
    }
    return answer;
}

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

    dfs_size(1, 0);
    timer = 0;
    dfs_decompose(1, 1);

    while (q--) {
        int op, x;
        cin >> op >> x;
        if (op == 0) {
            black[x] = !black[x];
            if (black[x])
                chain_black[top[x]].insert(dfn[x]);
            else
                chain_black[top[x]].erase(dfn[x]);
        } else {
            cout << query_first_black(x) << '\n';
        }
    }

    return 0;
}

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
169
170
171/**
 * 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 20:05
 * update_at: 2026-10-29 16:52
 */
#include <bits/stdc++.h>
using namespace std;

// 树链剖分（HLD）+ 线段树，节点与区间均为 1 下标。
// 线段树维护「区间内黑点的最小 dfn」，查询时从根侧往 v 侧逐段查重链段。
// 参考 rbook 模板 hld 的全局数组 + 普通函数写法，只保留本题需要的部分。

const int maxn = 100000 + 5;
const int INF = 0x3f3f3f3f;

int n, q;

/*------------------------ sgt 代码 开始 ------------------------*/
// 线段树：维护数组 base[1..n]，支持单点改、区间最小值。
// base[t] = 黑点 ? t : INF；内部节点存左右儿子的较小值。
int base[maxn];
int tree[maxn << 2];

int ls(int p) { return p << 1; }     // p 的左儿子 2p
int rs(int p) { return p << 1 | 1; } // p 的右儿子 2p+1

void push_up(int p) {
    tree[p] = min(tree[ls(p)], tree[rs(p)]);
}

void seg_build(int p, int l, int r) {
    if (l == r) {
        tree[p] = base[l];
        return;
    }
    int mid = (l + r) >> 1;
    seg_build(ls(p), l, mid);
    seg_build(rs(p), mid + 1, r);
    push_up(p);
}

// 单点改：把 dfn 位置 pos 的值改成 value。
void point_update(int pos, int value, int p, int l, int r) {
    if (l == r) {
        tree[p] = value;
        return;
    }
    int mid = (l + r) >> 1;
    if (pos <= mid) point_update(pos, value, ls(p), l, mid);
    else point_update(pos, value, rs(p), mid + 1, r);
    push_up(p);
}

// 区间最小值：不相交的分支返回 INF，不参与 min。
int range_min(int ql, int qr, int p, int l, int r) {
    if (qr < l || r < ql) return INF;     // 不相交
    if (ql <= l && r <= qr) return tree[p]; // 完全包含
    int mid = (l + r) >> 1;
    int answer = range_min(ql, qr, ls(p), l, mid);
    answer = min(answer, range_min(ql, qr, rs(p), mid + 1, r));
    return answer;
}
/*------------------------ sgt 代码 结束 ------------------------*/

/*------------------------ hld 代码 开始 ------------------------*/
// 树链剖分：g 存树，6 个核心数组维护树上信息。
vector<int> g[maxn];

int fa[maxn];  // fa[u]：父亲，根的 fa 为 0
int dep[maxn]; // dep[u]：深度，根为 1
int sz[maxn];  // sz[u]：子树大小（含自己）
int son[maxn]; // son[u]：重儿子，叶子为 0
int top[maxn]; // top[u]：所在重链的链头
int dfn[maxn]; // dfn[u]：线段树上的位置（DFS 新编号）
int node_at[maxn]; // node_at[t]：dfn 为 t 的原节点
int timer;

bool black[maxn]; // black[u]：节点 u 当前是否为黑点

void add_edge(int u, int v) {
    g[u].push_back(v);
    g[v].push_back(u);
}

// 第一遍 DFS：往下求 fa、dep，回溯时汇总 sz 并选出重儿子 son
void dfs1(int u, int father) {
    fa[u] = father;
    dep[u] = dep[father] + 1; // 根的 father 为 0、dep[0] 恒为 0，故根深度为 1
    sz[u] = 1;                // 先算上自己
    son[u] = 0;               // 叶子没有重儿子
    for (int v : g[u]) {
        if (v == father) continue;
        dfs1(v, u);
        sz[u] += sz[v];
        if (sz[v] > sz[son[u]]) son[u] = v;
    }
}

// 第二遍 DFS：重儿子优先分配 dfn，保证重链连续且链内 dfn 随深度递增
void dfs2(int u, int head) {
    top[u] = head;
    dfn[u] = ++timer;
    node_at[timer] = u;
    if (son[u]) dfs2(son[u], head);
    for (int v : g[u]) {
        if (v == fa[u] || v == son[u]) continue;
        dfs2(v, v);
    }
}

// 预处理入口：加完边之后调用一次。
void build(int root) {
    dfs1(root, 0);    // 填 fa / dep / sz / son
    timer = 0;        // 从 1 重新分配 dfn
    dfs2(root, root); // 填 top / dfn / node_at
    // 初始全白，所有叶子的值都是 INF
    for (int i = 1; i <= n; i++) base[i] = INF;
    seg_build(1, 1, n);
}

// 查询根 1 到 v 的路径上最浅的黑点编号，没有则返回 -1。
// 先把路径拆成若干重链段（从 v 向根收集），再按根侧到 v 侧的顺序逐段查最小值，
// 第一个出现的黑点就是答案（链内 dfn 与深度同序，区间最小值即最浅黑点）。
int query_first_black(int v) {
    vector<pair<int, int>> segments; // 每段是 [链头 dfn, 当前节点 dfn]
    int u = v;
    while (top[u] != 1) {
        segments.push_back(make_pair(dfn[top[u]], dfn[u]));
        u = fa[top[u]];
    }
    segments.push_back(make_pair(dfn[1], dfn[u])); // 最后一段一定包含根 1

    for (int i = (int)segments.size() - 1; i >= 0; i--) {
        int min_dfn = range_min(segments[i].first, segments[i].second, 1, 1, n);
        if (min_dfn != INF) return node_at[min_dfn];
    }
    return -1;
}
/*------------------------ hld 代码 结束 ------------------------*/

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

    cin >> n >> q;
    for (int i = 1; i <= n; i++) g[i].clear();

    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        add_edge(u, v);
    }

    build(1); // 根固定为 1

    while (q--) {
        int op, x;
        cin >> op >> x;
        if (op == 0) {
            // 取反颜色：黑点存自己的 dfn，白点存 INF
            black[x] = !black[x];
            point_update(dfn[x], black[x] ? dfn[x] : INF, 1, 1, n);
        } else {
            cout << query_first_black(x) << '\n';
        }
    }

    return 0;
}