摘要：
Lmnu表示距子画面子树的最上点最近的白点，其中u位于该点。rmnu表示距子画面子树的最低点最近的白点，其中u位于该点。打开一组，以保持与所有虚拟儿子都可以步行到的最近白点的距离。考虑俯卧撑。对于它的右儿子，考虑从这个点移动到它的虚拟儿子，或者通过它的左子树中深度最深的点。
lmn u 表示 u 所在splay子树最上方点距离最近的白点
rmn u 表示 u 所在splay子树最下方点距离最近的白点
开一个set维护所有虚儿子能走到的最近的白点的距离
考虑pushup，
对于它的右儿子，考虑要么从这个点走向它的虚儿子，要么通过它左子树中深度最大的点走。
对于它的左儿子要么从这个点走向它的虚儿子，要么通过它右子树的最浅点走。
#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);
// cout << S[1].size() << endl;
if( opt == 0 ) {
access( u ) , splay( u );
w[u] ^= 1;
pushup( u );
} else {
access( u ) , splay( u );
printf("%d
",rmn[u] > n ? -1 : rmn[u]);
}
}
}