You are given a tree (an acyclic undirected connected graph) with N nodes. The tree nodes are numbered from 1 to N. We define dist(a, b) as the number of edges on the path from node a to node b.
Each node has a color, white or black. All the nodes are black initially.
We will ask you to perfrom some instructions of the following form:
给出一棵n结点的树，边权为1，一开始每个点颜色都是黑色。
现有q个询问，每次询问会有两种操作：
1.0 i 改变i的颜色，黑变白，白变黑。
2.1 v 询问与v距离最近的白点，显然，当v颜色为白色时，答案是0。
For each "1 v" operation, print one integer representing its result. If there is no white node in the tree, you should write "-1".
这是自己写的第一个动态点分治题。
堆
在每个点上都建立一个可删除堆（手写也可以，像我一样偷懒的话两个系统堆模拟也行，一个记录队列中加入的，一个记录堆中被删除的元素，每次遇到队首相同的元素，就同时弹出即可！）这样每个点都可以（近乎）\(O(1)\)的求出一个点上的答案，不过这样的话，更新的复杂度会直接爆炸！
点分治
动态点分治的用处这时就体现出来了，就只用更新点分治树树根到该点的路径上的所有点即可，复杂度为\(O(logn)\)，然后在询问的时候，同理在这条路径上，枚举每一个点，将该点队列上的最大值再加上该点到询问点上的距离的值求出，一路\(min\)上去最后得到的就是答案，复杂度同样为\(O(logn)\)，枚举该路径只要从当前点开始在点分治树上跳父亲即可
最后就是求两点之间的路径长度，应该不难，用\(LCA\)法即可，\(lca\)可以直接预处理，用跳重链法等都可以，有
dis(x,y)=dep[x]+dep[y]-dep[lca]*2\(dep\)为该点深度。
#include<cstdio>
#include<cstring>
#include<queue>
#define FOR(i,l,r) for(int i=l,END=r;i<=END;i++)
#define DOR(i,r,l) for(int i=r,END=l;i>=END;i--)
#define loop(i,n) for(int i=0,END=n;i<END;i++)
#define mms(a,x) memset(a,x,sizeof a)
#define pf printf
#define sf scanf
using namespace std;
const int N=1e5+5;
struct Graph{//正向表
int tot,to[N<<1],nxt[N<<1],head[N];
void add(int x,int y){tot++;to[tot]=y;nxt[tot]=head[x];head[x]=tot;}
void clear(){mms(head,-1);tot=0;}
#define EOR(i,x) for(int i=G.head[x];i!=-1;i=G.nxt[i])
}G;
struct Distance_Calculator{//计算两点的路径
int sz[N],son[N],fa[N],dep[N],top[N];
void dfs(int x,int f){
fa[x]=f,dep[x]=dep[f]+1;
sz[x]=1,son[x]=0;
EOR(i,x){
int v=G.to[i];
if(v==f)continue;
dfs(v,x);
sz[x]+=sz[v];
if(sz[son[x]]<sz[v])son[x]=v;
// pf("x:%d son[x]:%d\n",x,son[x]);
}
}
void top_dfs(int x,int f,int tp){
// pf("x:%d f:%d tp:%d son[x]:%d\n",x,f,tp,son[x]);
top[x]=tp;
if(son[x])top_dfs(son[x],x,tp);
EOR(i,x){
int v=G.to[i];
if(v==f||v==son[x])continue;
top_dfs(v,x,v);
}
}
int LCA(int x,int y){//跳重链
while(top[x]!=top[y]){
if(dep[top[x]]>dep[top[y]])x=fa[top[x]];
else y=fa[top[y]];
}
return dep[y]>dep[x]?x:y;
}
int dist(int x,int y){return dep[x]+dep[y]-(dep[LCA(x,y)]<<1);}
void init(){
dfs(1,0);
top_dfs(1,0,1);
}
}D;
int fa[N];
struct Heap{//可删除堆
priority_queue<int,vector<int>,greater<int> >Q,del;
void Del(int x){del.push(x);}
void Erase(){while(!del.empty()&&del.top()==Q.top())Q.pop(),del.pop();}
void Push(int x){Q.push(x);}
bool Empty(){Erase();return Q.empty();}
int Top(){Erase();if(Empty())return -1;else return Q.top();}
}H[N];
int n;
bool vis[N];
int sz[N],mx[N],center,t_sz;
void get_center(int x,int f){//找重心
sz[x]=1,mx[x]=0;
EOR(i,x){
int v=G.to[i];
if(v==f||vis[v])continue;
get_center(v,x);
sz[x]+=sz[v];
mx[x]=max(mx[x],sz[v]);
}
mx[x]=max(mx[x],t_sz-sz[x]);
if(!center||mx[center]>mx[x])center=x;
}
void DAC(int x){//预处理点分树
vis[x]=1;
EOR(i,x){
int v=G.to[i];
if(vis[v])continue;
t_sz=sz[v],center=0;
get_center(v,x);
fa[center]=x;//关键
DAC(center);
}
}
bool col[N];//记录颜色
void insert(int x){
H[x].Push(0);//加入自己本身
for(int i=fa[x];i;i=fa[i]){//暴跳父亲，更新
int dis=D.dist(x,i);
H[i].Push(dis);
}
}
void erase(int x){
H[x].Del(0);//删除自己本身
for(int i=fa[x];i;i=fa[i]){//暴跳父亲，删除
int dis=D.dist(x,i);
H[i].Del(dis);
}
}
int Query(int x){//询问
int ret=2e9;
for(int i=x;i;i=fa[i]){
int dis=D.dist(x,i);
int dis2=H[i].Top();
if(dis2==-1)continue;
ret=min(ret,dis2+dis);
}
return ret==2e9?-1:ret;
}
int main(){
G.clear();
sf("%d",&n);
FOR(i,1,n-1){
int x,y;
sf("%d%d",&x,&y);
G.add(x,y);
G.add(y,x);
}
t_sz=n,get_center(1,0);
DAC(center);
D.init();
//以上为预处理
int q;
sf("%d",&q);
while(q--){
int op,v;
sf("%d%d",&op,&v);
if(!op){
col[v]^=1;
if(col[v])insert(v);
else erase(v);
}
else pf("%d\n",Query(v));
}
return 0;
}Query on a tree V（SPOJ - QTREE5）
原文：https://www.cnblogs.com/Heinz/p/10464218.html