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
| #include <iostream>
#include <cmath>
#include <queue>
#define maxn 100010
#define sqrtn 400
using namespace std;
int n, m;
struct Edge {
int to, next;
} e[maxn * 2]; int c1, head[maxn];
inline void add_edge(int u, int v) {
e[c1].to = v; e[c1].next = head[u]; head[u] = c1++;
}
int id[maxn * 2], in[maxn], dep[maxn];
void dfs(int u, int fa) {
static int cnt = 0;
id[++cnt] = u; in[u] = cnt;
for (int i = head[u]; ~i; i = e[i].next) {
int v = e[i].to; if (v == fa) continue;
dep[v] = dep[u] + 1; dfs(v, u); id[++cnt] = u;
}
}
inline int st_min(int l, int r) { return in[l] < in[r] ? l : r; }
int st[maxn * 2][21], Log[maxn * 2];
void init_st(int n) { Log[0] = -1;
for (int i = 1; i <= n; ++i) Log[i] = Log[i >> 1] + 1;
for (int i = 1; i <= n; ++i) st[i][0] = id[i];
for (int j = 1; j <= 20; ++j)
for (int i = 1; i + (1 << j) - 1 <= n; ++i)
st[i][j] = st_min(st[i][j - 1], st[i + (1 << j - 1)][j - 1]);
}
inline int get_lca(int l, int r) {
l = in[l]; r = in[r]; if (l > r) swap(l, r);
int k = Log[r - l + 1];
return st_min(st[l][k], st[r - (1 << k) + 1][k]);
}
inline int D(int x, int y) { return dep[x] + dep[y] - 2 * dep[get_lca(x, y)]; }
int blo, num, l[sqrtn], r[sqrtn], bl[maxn];
void init_blo(int n) {
blo = sqrt(n); num = (n + blo - 1) / blo;
for (int i = 1; i <= n; ++i) bl[i] = (i - 1) / blo + 1;
for (int i = 1; i <= num; ++i) {
l[i] = (i - 1) * blo + 1;
r[i] = i * blo;
} r[num] = n;
}
struct Query {
int opt, x;
} Q[maxn];
int ans[maxn];
int dis[maxn]; bool vis[maxn];
void bfs(int k) {
fill(dis, dis + maxn, 0);
fill(vis, vis + maxn, 0);
queue<int> Q;
for (int i = l[k]; i <= r[k]; ++i) {
int opt = ::Q[i].opt, x = ::Q[i].x;
if (opt == 1) {
dis[x] = 0; vis[x] = 1;
Q.push(x);
}
}
while (!Q.empty()) {
int u = Q.front(); Q.pop();
if (dis[u] < ans[u]) ans[u] = dis[u];
for (int i = head[u]; ~i; i = e[i].next) {
int v = e[i].to; if (vis[v]) continue;
vis[v] = 1; dis[v] = dis[u] + 1; Q.push(v);
}
}
}
int main() { fill(head, head + maxn, -1);
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
cin >> n >> m;
for (int i = 1; i < n; ++i) {
int x, y; cin >> x >> y;
add_edge(x, y); add_edge(y, x);
} dep[1] = 1; dfs(1, 0); init_st(2 * n - 1); init_blo(m); bl[0] = 1;
for (int i = 1; i <= n; ++i) ans[i] = D(i, 1);
for (int i = 1; i <= m; ++i) {
int opt, x; cin >> opt >> x; Q[i] = { opt, x };
if (bl[i] != bl[i - 1]) bfs(bl[i - 1]);
if (opt == 2) {
int ans = ::ans[x];
for (int j = l[bl[i]]; j < i; ++j)
if (Q[j].opt == 1) ans = min(ans, D(x, Q[j].x));
cout << ans << "\n";
}
}
return 0;
}
|