思路
可以树剖可以LCT，树剖就是每个重链开一个SET维护一下黑点的深度
代码
#include#include #include using namespace std;struct Node{ int son[2],sum,inv,fa,val;}SPT[100100];int n,q;bool isrl(int o){ return SPT[SPT[o].fa].son[1]==o;}bool isroot(int o){ return SPT[SPT[o].fa].son[0]!=o&&SPT[SPT[o].fa].son[1]!=o;}void pushup(int o){ SPT[o].sum=SPT[SPT[o].son[0]].sum+SPT[o].val+SPT[SPT[o].son[1]].sum;}void pushdown(int o){ if(SPT[o].inv){ SPT[SPT[o].son[0]].inv^=1; SPT[SPT[o].son[1]].inv^=1; swap(SPT[o].son[0],SPT[o].son[1]); SPT[o].inv^=1; }}void rorate(int o){ if(isroot(o)) return; int f=SPT[o].fa; int g=SPT[f].fa; pushdown(f); pushdown(o); int which=isrl(o); if(!isroot(f)) SPT[g].son[SPT[g].son[1]==f]=o; SPT[o].fa=g; SPT[f].son[which]=SPT[o].son[which^1]; SPT[SPT[o].son[which^1]].fa=f; SPT[o].son[which^1]=f; SPT[f].fa=o; pushup(f); pushup(o);}void allpush(int o){ if(!isroot(o)) allpush(SPT[o].fa); pushdown(o);}void splay(int o){ allpush(o); for(int f;!isroot(o);rorate(o)){ if(!isroot(f=SPT[o].fa)) rorate((isrl(f)==isrl(o))?f:o); }}void access(int o){ for(int y=0;o;o=SPT[y=o].fa) splay(o),SPT[o].son[1]=y,pushup(o);}void makeroot(int o){ access(o); splay(o); SPT[o].inv^=1; pushdown(o);}int findroot(int o){ access(o); splay(o); pushdown(o); while(SPT[o].son[0]) pushdown(o=SPT[o].son[0]); return o;}void link(int x,int y){ makeroot(x); if(findroot(y)!=x) SPT[x].fa=y;}int dfs(int x){ if(SPT[x].val){ if(SPT[SPT[x].son[0]].sum) return dfs(SPT[x].son[0]); else return x; } else{ if(SPT[SPT[x].son[0]].sum) return dfs(SPT[x].son[0]); else if(SPT[SPT[x].son[1]].sum) return dfs(SPT[x].son[1]); }}int query(int x){ access(x); splay(x); pushdown(x); if(!(SPT[SPT[x].son[0]].sum+SPT[x].val)) return -1; if(SPT[x].val&&(!SPT[SPT[x].son[0]].sum)) return x; return dfs(SPT[x].son[0]);}int main(){ scanf("%d %d",&n,&q); for(int i=1;i