题意：给你一棵树， 然后树上的点都有颜色，且原来为黑，现在有2个操作，1 改变某个点的颜色， 2 询问树上的白点到u点的最短距离是多少。
题解：
这里用的还是边分治的方法。
把所有东西都抠出来， 然后每次询问的时候都访问每幅分割图的另外一侧。
代码：
#include<bits/stdc++.h>
using namespace std;
#define Fopen freopen("_in.txt","r",stdin); freopen("_out.txt","w",stdout);
#define LL long long
#define ULL unsigned LL
#define fi first
#define se second
#define pb push_back
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define lch(x) tr[x].son[0]
#define rch(x) tr[x].son[1]
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
typedef pair<int,int> pll;
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const LL mod = (int)1e9+;
const int N = 2e5 + ;
struct Node{
int head[N], to[N<<], nt[N<<], ct[N<<];
int tot;
void init(){
memset(head, -, sizeof(head));
tot = ;
}
void add(int u, int v, int cost){
ct[tot] = cost;
to[tot] = v;
nt[tot] = head[u];
head[u] = tot++;
}
}e[];
int n, m, white[N], cut[N<<];
void rebuild(int o, int u){
int ff = ;
for(int i = e[].head[u]; ~i; i = e[].nt[i]){
int v = e[].to[i];
if(o == v) continue;
if(!ff){
e[].add(u, v, );
e[].add(v, u, );
ff = u;
}
else {
++n;
e[].add(ff, n, ); e[].add(n, ff, );
e[].add(n, v, ); e[].add(v, n, );
ff = n;
}
rebuild(u, v);
}
}
int sz[N], minval, id;
void get_edge(int o, int u, int num){
sz[u] = ;
for(int i = e[].head[u]; ~i; i = e[].nt[i]){
int v = e[].to[i];
if(v == o || cut[i>>]) continue;
get_edge(u, v, num);
sz[u] += sz[v];
int tmp = max(sz[v], num - sz[v]);
if(tmp < minval){
minval = tmp;
id = i;
}
}
}
int k = , op;
vector<pll> vc[N];
priority_queue<pll, vector<pll>, greater<pll> > pq[N<<][];
int wedge[N<<];
int mm;
void dfs2(int o, int u, int w){
vc[u].pb(pll(k*op, w));
sz[u] = ;
for(int i = e[].head[u]; ~i; i = e[].nt[i]){
int v = e[].to[i];
if(v == o || cut[i>>]) continue;
dfs2(u, v, w + e[].ct[i]);
sz[u] += sz[v];
}
}
void solve(int u, int num){
if(num <= ) return ;
minval = inf;
get_edge(, u, num);
int nid = id;
cut[nid>>] = ;
++k;
op = ;
dfs2(, e[].to[nid], );
op = -;
dfs2(, e[].to[nid^], );
wedge[k] = e[].ct[nid];
solve(e[].to[nid], sz[e[].to[nid]]);
solve(e[].to[nid^], sz[e[].to[nid^]]);
}
void Update(int k){
while(!pq[k][].empty() && !white[pq[k][].top().se]) pq[k][].pop();
while(!pq[k][].empty() && !white[pq[k][].top().se]) pq[k][].pop();
}
void setwhite(int u){
for(int i = ; i < vc[u].size(); i++){
int k = vc[u][i].fi, w = vc[u][i].se;
if(k < ) pq[-k][].push(pll(w,u));
else pq[k][].push(pll(w,u));
Update(abs(k));
}
}
void setblack(int u){
for(int i = ; i < vc[u].size(); i++){
int k = vc[u][i].fi;
Update(abs(k));
}
}
int Find(int u){
int ret = inf;
for(int i = ; i < vc[u].size(); i++){
int k = vc[u][i].fi, w = vc[u][i].se;
if(k < && !pq[-k][].empty())
ret = min(ret, w+wedge[-k]+pq[-k][].top().fi);
if(k > && !pq[k][].empty())
ret = min(ret, w+wedge[k]+pq[k][].top().fi);
}
return ret;
}
int main(){
e[].init(); e[].init();
scanf("%d", &n);
int u, v;
for(int i = ; i < n; i++){
scanf("%d%d", &u, &v);
e[].add(u, v, ); e[].add(v, u, );
}
memset(white, , sizeof(white));
rebuild(, );
solve(, n);
int num = , op;
scanf("%d", &m);
while(m--){
scanf("%d%d", &op, &v);
if(op == ){
white[v] ^= ;
if(white[v]){
setwhite(v);
num++;
}
else {
setblack(v);
num--;
}
}
else {
if(num == ) puts("-1");
else if(white[v]) puts("");
else {
printf("%d\n", Find(v));
}
}
}
return ;
}