题意翻译
你被给定一棵n个点的树，点从1到n编号。每个点可能有两种颜色：黑或白。我们定义dist(a,b)为点a至点b路径上的边个数。
一开始所有的点都是黑色的。
要求作以下操作：
0 i 将点i的颜色反转（黑变白，白变黑）
1 v 询问dist(u,v)的最小值。u点必须为白色（u与v可以相同），显然如果v是白点，查询得到的值一定是0。
特别地，如果作'1'操作时树上没有白点，输出-1。
题解
是QTREE4的弱化版诶……
具体的思路可以看看Qtree4的->这里
注意把求最大改成求最小，还有只需要到点的最短距离，不需要维护子树里的答案了
然后查询的时候本来打算makeroot的……后来发现太麻烦了……直接access+splay，然后查询rmx即可（因为已经在这个splay里深度最大了）
1 //minamoto 2 #include<bits/stdc++.h> 3 #define inf 0x3f3f3f3f 4 using namespace std; 5 #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++) 6 char buf[1<<21],*p1=buf,*p2=buf; 7 inline int read(){ 8 #define num ch-'0' 9 char ch;bool flag=0;int res; 10 while(!isdigit(ch=getc())) 11 (ch=='-')&&(flag=true); 12 for(res=num;isdigit(ch=getc());res=res*10+num); 13 (flag)&&(res=-res); 14 #undef num 15 return res; 16 } 17 char obuf[1<<24],*o=obuf; 18 inline void print(int x){ 19 if(x>9) print(x/10); 20 *o++=x%10+48; 21 } 22 const int N=100005; 23 int ver[N<<1],head[N],Next[N<<1]; 24 int rev[N],fa[N],ch[N][2],w[N],col[N],lmn[N],rmn[N],len[N],val[N]; 25 multiset<int> s[N]; 26 int n,q,white=0,tot; 27 #define ls ch[x][0] 28 #define rs ch[x][1] 29 inline int fir(multiset<int> &s){return s.size()?*s.begin():inf;} 30 inline int min(int x,int y,int z){return min(x,min(y,z));} 31 inline bool add(int u,int v){ver[++tot]=v,Next[tot]=head[u],head[u]=tot;} 32 inline bool isroot(int x){return ch[fa[x]][0]!=x&&ch[fa[x]][1]!=x;} 33 inline void init(){for(int i=0;i<=n;++i) lmn[i]=rmn[i]=w[i]=inf;} 34 inline void pushr(int x){ 35 rev[x]^=1,swap(ls,rs),swap(lmn[x],rmn[x]); 36 } 37 inline void pushup(int x){ 38 if(!x) return; 39 len[x]=len[ls]+len[rs]+val[x]; 40 lmn[x]=min(lmn[ls],len[ls]+val[x]+min(w[x],fir(s[x]),lmn[rs])); 41 rmn[x]=min(rmn[rs],len[rs]+min(w[x],fir(s[x]),rmn[ls]+val[x])); 42 } 43 inline void pushdown(int x){ 44 if(x&&rev[x]){ 45 pushr(ls),pushr(rs),rev[x]=0; 46 } 47 } 48 void rotate(int x){ 49 int y=fa[x],z=fa[y],d=ch[y][1]==x; 50 if(!isroot(y)) ch[z][ch[z][1]==y]=x; 51 fa[x]=z,fa[y]=x,fa[ch[x][d^1]]=y,ch[y][d]=ch[x][d^1],ch[x][d^1]=y,pushup(y); 52 } 53 void down(int x){ 54 if(!isroot(x)) down(fa[x]); 55 pushdown(x); 56 } 57 void splay(int x){ 58 down(x); 59 for(int y=fa[x],z=fa[y];!isroot(x);y=fa[x],z=fa[y]){ 60 if(!isroot(y)) 61 ((ch[z][1]==y)^(ch[y][1]==x))?rotate(x):rotate(y); 62 rotate(x); 63 } 64 pushup(x); 65 } 66 void access(int x){ 67 for(int y=0;x;x=fa[y=x]){ 68 splay(x); 69 if(rs) s[x].insert(lmn[rs]); 70 if(y) s[x].erase(s[x].find(lmn[y])); 71 rs=y,pushup(x); 72 } 73 } 74 void modify(int x){ 75 access(x),splay(x); 76 col[x]^=1,w[x]=col[x]?0:inf; 77 col[x]?(++white):(--white); 78 pushup(x); 79 } 80 int query(int x){ 81 access(x),splay(x); 82 return rmn[x]; 83 } 84 void dfs(int u){ 85 for(int i=head[u];i;i=Next[i]){ 86 int v=ver[i]; 87 if(v==fa[u]) continue; 88 fa[v]=u,val[v]=1,dfs(v); 89 s[u].insert(lmn[v]); 90 } 91 pushup(u); 92 } 93 int main(){ 94 //freopen("testdata.in","r",stdin); 95 n=read();init(); 96 for(int i=1;i<n;++i){ 97 int u=read(),v=read(); 98 add(u,v),add(v,u); 99 } 100 dfs(1);q=read(); 101 while(q--){ 102 int op=read(),x=read(); 103 if(op){ 104 if(!white) *o++='-',*o++='1'; 105 else if(col[x]) *o++='0'; 106 else print(query(x)); 107 *o++='\n'; 108 } 109 110 else modify(x); 111 } 112 fwrite(obuf,o-obuf,1,stdout); 113 return 0; 114 }