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
| #include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<set>
using namespace std;
#define MAXN 100006
int n , m;
int ch[MAXN][2] , siz[MAXN] , fa[MAXN] , lmn[MAXN] , rmn[MAXN];
int w[MAXN];
multiset<int> S[MAXN];
bool notr( int u ) {
return ( ch[fa[u]][0] == u ) || ( ch[fa[u]][1] == u );
}
void pushup( int u ) {
int ls = ch[u][0] , rs = ch[u][1];
siz[u] = siz[ls] + siz[rs] + 1;
if( w[u] ) {
lmn[u] = min( lmn[ls] , siz[ls] );
rmn[u] = min( rmn[rs] , siz[rs] );
return;
}
int t = S[u].empty() ? 0x3f3f3f3f : *S[u].begin();
lmn[u] = min( lmn[ls] , lmn[rs] + siz[ls] + 1 );
rmn[u] = min( rmn[rs] , rmn[ls] + siz[rs] + 1 );
lmn[u] = min( lmn[u] , t + siz[ls] ) , rmn[u] = min( rmn[u] , t + siz[rs] );
}
void rotate( int x ) {
int f = fa[x] , g = fa[f] , w = ch[fa[x]][1] == x;
int wf = ch[g][1]==f , k = ch[x][w^1];
if( notr(f) ) ch[g][wf] = x; ch[f][w] = k , ch[x][w^1] = f;
fa[f] = x , fa[k] = f , fa[x] = g;
pushup( f ) , pushup( x );
}
void splay( int x ) {
int f , g;
while( notr( x ) ) {
f = fa[x] , g = fa[f];
if( notr( f ) )
rotate( (ch[f][0]==x)^(ch[g][0]==f) ? x : f );
rotate( x );
}
}
void access( int x ) {
for( int p = 0 ; x ; ( p = x , x = fa[x] ) ) {
splay( x );
if( ch[x][1] ) S[x].insert( 1 + lmn[ch[x][1]] );
if( p ) S[x].erase( S[x].find( 1 + lmn[p] ) );
ch[x][1] = p , pushup( x );
}
}
int head[MAXN] , nex[MAXN << 1] , to[MAXN << 1] , ecn;
void ade( int u , int v ) {
nex[++ ecn] = head[u] , to[ecn] = v , head[u] = ecn;
}
void dfs( int u , int f ) {
fa[u] = f;
for( int i = head[u] ; i ; i = nex[i] ) {
int v = to[i];
if( v == f ) continue;
dfs( v , u );
S[u].insert( 1 + 0x3f3f3f3f );
}
}
int main() {
cin >> n;
for( int i = 1 , u , v ; i < n ; ++ i ) {
scanf("%d%d",&u,&v);
ade( u , v ) , ade( v , u );
}
dfs( 1 , 0 );
lmn[0] = rmn[0] = 0x3f3f3f3f;
for( int i = 1 ; i <= n ; ++ i )
lmn[i] = rmn[i] = 0x3f3f3f3f , siz[i] = 1;
cin >> m;
int opt , u;
while( m-- ) {
scanf("%d%d",&opt,&u);
if( opt == 0 ) {
access( u ) , splay( u );
w[u] ^= 1;
pushup( u );
} else {
access( u ) , splay( u );
printf("%d\n",rmn[u] > n ? -1 : rmn[u]);
}
}
}
|
