动态点分治和动态边分治用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
     
      #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
      
       il void rd(T &x){    char ch;x=0;bool fl=false;    while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);    for(x=numb;isdigit(ch=getchar());x=x*10+numb);    (fl==true)&&(x=-x);}template
       
        il void output(T x){
   if(x/10)output(x/10);putchar(x%10+'0');}template
        
         il void ot(T x){
   if(x<0) putchar('-'),x=-x;output(x);putchar(' ');}template
         
          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=100000+5;const int inf=0x3f3f3f3f;int n,q;struct node{    int ch[2],fa;    int lmn,rmn;    int co;//1:white 0:black    int sz;    multiset
          
           s; multiset
           
            ::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[1] "<
             
              <<" fa "<
              
               <
              
             
            
           
          
         
        
       
      
     

 

见着拆招，pushup不好处理，就直接记录lmn和rmn，lmn用于access更新set，rmn用于查询答案。

如果要换根，还要考虑swap(lmn,rmn)