动态点分治和动态边分治用Qtree4的做法即可。
LCT：
换根后，求子树最浅的白点深度。
但是也可以不换根。类似平常换根的往上g，往下f的拼凑
考虑深度的pushup必须考虑原树结构的联系，而ch[0],ch[1]又不是直接的前驱后继，每次pushup还要找前驱后继答案，还不如直接记下来。
故，节点里维护：
1.sz，大小
2.color节点颜色
3.set每个虚儿子贡献的最浅深度
4.lmn，rmn，当前x的splay子树最浅点和最深点的，展开成的实链的范围内的答案。
也就是：
pushup：
后面的就是跨过x的拼凑。top是虚儿子set的最小值
access：
虚实儿子转化
修改，access，splay，t[x].co^1
查询：access,splay, cout<<t[x].rmn
代码：
#include<bits/stdc++.h>
#define reg register int
#define il inline
#define fi first
#define se second
#define mk(a,b) make_pair(a,b)
#define numb (ch^'0')
using namespace std;
typedef long long ll;
template<class T>il void rd(T &x){
char ch;x=;bool fl=false;
while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);
for(x=numb;isdigit(ch=getchar());x=x*+numb);
(fl==true)&&(x=-x);
}
template<class T>il void output(T x){if(x/)output(x/);putchar(x%+'');}
template<class T>il void ot(T x){if(x<) putchar('-'),x=-x;output(x);putchar(' ');}
template<class T>il void prt(T a[],int st,int nd){for(reg i=st;i<=nd;++i) ot(a[i]);putchar('\n');} namespace Miracle{
const int N=+;
const int inf=0x3f3f3f3f;
int n,q;
struct node{
int ch[],fa;
int lmn,rmn;
int co;//1:white 0:black
int sz;
multiset<int>s;
multiset<int>::iterator it;
int top(){
if(s.size()) return *s.begin();
return inf;
}
void ins(int c){
s.insert(c);
}
void dele(int c){
it=s.lower_bound(c);
if(it!=s.end()) s.erase(it);
}
void op(){
cout<<" ch[0] "<<ch[]<<" ch[1] "<<ch[]<<" fa "<<fa<<endl;
cout<<" co "<<co<<" sz "<<sz<<endl;
cout<<" lmn "<<lmn<<" rmn "<<rmn<<endl;
cout<<" s.size() "<<s.size()<<endl;
}
}t[N];
int nrt(int x){
return t[t[x].fa].ch[]==x||t[t[x].fa].ch[]==x;
}
void pushup(int x){
if(!x) return;
t[x].sz=t[t[x].ch[]].sz+t[t[x].ch[]].sz+;
t[x].lmn=min(t[t[x].ch[]].lmn,t[t[x].ch[]].sz+min(t[x].co?:inf,min(t[x].top(),t[t[x].ch[]].lmn+)));
t[x].rmn=min(t[t[x].ch[]].rmn,t[t[x].ch[]].sz+min(t[x].co?:inf,min(t[x].top(),t[t[x].ch[]].rmn+)));
}
void rotate(int x){
int y=t[x].fa,d=t[y].ch[]==x;
t[t[y].ch[d]=t[x].ch[!d]].fa=y;
if(nrt(y)) t[t[x].fa=t[y].fa].ch[t[t[y].fa].ch[]==y]=x;
else t[x].fa=t[y].fa;
t[t[x].ch[!d]=y].fa=x;
pushup(y);
}
void splay(int x){
int y,z;
while(nrt(x)){
y=t[x].fa,z=t[y].fa;
if(nrt(y)){
rotate((t[y].ch[]==x)==(t[z].ch[]==y)?y:x);
}
rotate(x);
}
pushup(x);
}
void access(int x){
// cout<<" access "<<x<<endl;
for(reg y=;x;y=x,x=t[x].fa){
splay(x);
if(y) t[x].dele(t[y].lmn+);
if(t[x].ch[]) t[x].ins(t[t[x].ch[]].lmn+);
t[x].ch[]=y;
pushup(x);
// cout<<" x "<<x<<" y "<<y<<endl;
// t[x].op();
}
}
struct edge{
int nxt,to;
}e[*N];
int hd[N],cnt;
void add(int x,int y){
e[++cnt].nxt=hd[x];
e[cnt].to=y;
hd[x]=cnt;
}
void dfs(int x,int fa){
t[x].sz=;
t[x].lmn=inf;t[x].rmn=inf;
t[x].co=;
for(reg i=hd[x];i;i=e[i].nxt){
int y=e[i].to;
if(y==fa) continue;
t[y].fa=x;
dfs(y,x);
}
}
int main(){
rd(n);
int x,y;
for(reg i=;i<n;++i){
rd(x);rd(y);
add(x,y);add(y,x);
}
dfs(,);
rd(q);
int op;
t[].lmn=inf,t[].sz=;
t[].rmn=inf;t[].co=;
while(q--){
rd(op);rd(x);
if(!op){
access(x);splay(x);
t[x].co^=;
pushup(x);
// t[x].op();
}else{
access(x);splay(x);
// t[x].op();
printf("%d\n",t[x].rmn<=n?t[x].rmn:-);
}
}
return ;
} }
signed main(){
Miracle::main();
return ;
} /*
Author: *Miracle*
Date: 2019/3/14 21:49:23
*/
见着拆招，pushup不好处理，就直接记录lmn和rmn，lmn用于access更新set，rmn用于查询答案。
如果要换根，还要考虑swap(lmn,rmn)