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
| #include <bits/stdc++.h>
#define MAX_N 100000
using namespace std;
int n, m;
vector<int> adj[MAX_N + 1];
int LCA[MAX_N + 1][22];
int sz[MAX_N + 1];
int level[MAX_N + 1];
int tree[MAX_N + 1];
bool vis[MAX_N + 1];
bool color[MAX_N + 1];
multiset<int> s[MAX_N + 1];
void dfs(int u) {
for(auto& v : adj[u])
if(level[v] == 0) {
LCA[v][0] = u;
level[v] = level[u] + 1;
dfs(v);
}
}
int lca(int u, int v) {
if(level[u] < level[v]) swap(u, v);
int diff = level[u] - level[v];
for(int j = 0; diff; j++, diff /= 2) {
if(diff & 1) u = LCA[u][j];
}
if(u != v) {
for(int j = 21; j >= 0; j--) {
if(LCA[u][j] != LCA[v][j]) {
u = LCA[u][j];
v = LCA[v][j];
}
}
u = LCA[u][0];
}
return u;
}
int getDist(int u, int v){
return level[u] + level[v] - 2 * level[lca(u, v)];
}
int getSize(int u, int p) {
sz[u] = 1;
for(auto& v : adj[u]) {
if(!vis[v] and v != p)
sz[u] += getSize(v, u);
}
return sz[u];
}
int getCent(int u, int p, int size) {
for(auto& v : adj[u]) {
if(!vis[v] and v != p and sz[v] * 2 > size)
return getCent(v,u,size);
}
return u;
}
void centroidDecomposition(int u, int p) {
int cent = getCent(u, p, getSize(u, -1) / 2);
tree[cent] = p;
vis[cent] = true;
for(auto& v : adj[cent])
if(!vis[v])
centroidDecomposition(v, cent);
}
void init() {
dfs(1);
for(int j=0; j < 21; j++){
for(int i=1; i<=n; i++){
LCA[i][j+1] = LCA[LCA[i][j]][j];
}
}
centroidDecomposition(1, -1);
}
void update(int u) {
color[u] = !color[u];
int v = u;
while(v != -1) {
int d = getDist(u, v);
if(color[u]) s[v].insert(d);
else s[v].erase(s[v].find(d));
v = tree[v];
}
}
int qry(int u) {
int v = u, res = INT_MAX;
while(v != -1) {
int d = getDist(u, v);
if(!s[v].empty()) res = min(res, d + *s[v].begin());
v = tree[v];
}
return res == INT_MAX ? -1 : res;
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> n;
for(int i = 1, u, v; i < n; i++) {
cin>>u>>v;
adj[u].push_back(v);
adj[v].push_back(u);
}
init();
cin>>m;
int op, u;
while(m--) {
cin>>op>>u;
if(op == 1) update(u);
else cout<<qry(u)<<"\n";
}
}
|
