P2056 [ZJOI2007]捉迷藏

动态点分治，点分树。

具体做法应该在题解里面已经很清楚了，这里久不再赘述了。写一下细节问题。

1. 在递归寻找重心的时候，没有必要使用 $f$ 数组，比较这两种写法，其实都是一样的：

   当然，如果后面有要用到 $f$ 数组，当我没说。

   inline void getroot(ll x,ll fa){
   	son[x]=1;f[x]=0;
   	for(register int i=hd[x];i;i=e[i].nx)
   		if(e[i].to!=fa&&!vit[e[i].to]){
   			getroot(e[i].to,x);
   			son[x]+=son[e[i].to];
   			f[x]=max(f[x],son[e[i].to]);
   		}
   	f[x]=max(f[x],sum-son[x]);
   	if(f[x]<f[root])    root=x;
   }
   

   inline void findroot(ll x,ll fat){
       siz[x]=1;
       ll mx=0;
       for(register int i=hd[x];i;i=e[i].nx){
           ll to=e[i].to;
           if(vit[to]||to==fat)    continue;
           findroot(to,x);
           siz[x]+=siz[to];
           mx=max(mx,siz[to]);
       }
       if(max(mx,tot-siz[x])<=tot/2)   root=x;
   }
   

2. 在更新点分树上的点 $x$ 的时候，不仅要把 $x$ 的儿子的值插到 $x$ 所对应的堆里面，还要更新 $x$ 在点分树上的父亲 $fa[x]$ 的值。但由于是先把 $son[x]$ 传到 $x$ ，$x$ 再传 $fa[x]$ ，所以直接插 $x$ 堆里的最大值就可以了，记得把 $x$ 那个 $0$ 插上。

   既要开 $lta$ （维护全局答案）又要开 $ltas$ （维护每个点的答案）也是方便在开关灯的时候更新（在 $lta$ 中插入和删除）

   inline void dfs(ll x,ll fat,ll dp){
       gdp=dp;
       bfs(x);
       findroot(x,0);
       rdp[root]=dp;
       for(register int i=0;i<tot;++i)
           df[root].insert(dis[q[i]][dp]);
           //维护root儿子中的最大值
       fa[root]=fat;//fat是root点分树上的父亲
       vit[root]=1;
       ll tmp=root;
       for(register int i=hd[root];i;i=e[i].nx){
           if(vit[e[i].to])    continue;
           dfs(e[i].to,tmp,dp+1);
       }
       if(fat)
           ch[fat].insert(df[tmp].getmax());
       //上传到点分树上的父亲
       ch[tmp].insert(0);
       lta.insert(ltas[tmp]=ch[tmp].getmax()+ch[tmp].getsecond());
   }
   

3. 在改变 $x$ 的开关灯状态时，从 $x$ 往点分树上的父亲一步步跳，每跳一步分别更新 $lta$ 、$ltas$ 的值，再更新 $fa[x]$ 的值。

       for(register int ac=1;ac<=qt;++ac){
           cin>>op;
           getchar();
           if(op=='G'){
               if(line==1)     printf("0\n");
               else        
                   if(line==0) printf("-1\n");
                   else        printf("%lld\n",lta.getmax());
           }
           else{
               cin>>u;
               if(shut[u])
                   ch[u].insert(0),++line;
               else    
                   ch[u].remove(0),--line;
               ll cur=u;
               while(cur){
                   ll tmp=ch[cur].getmax()+ch[cur].getsecond();
                   if(tmp!=ltas[cur]){
                       lta.remove(ltas[cur]);
                       lta.insert(ltas[cur]=tmp);
                   }
                   if(!fa[cur])    break;
                   ll dp=rdp[cur];
                   tmp=df[cur].getmax();
                   if(shut[u])     df[cur].insert(dis[u][dp]);
                   else            df[cur].remove(dis[u][dp]);
                   ll pmt=df[cur].getmax();
                   if(tmp!=pmt){
                       ch[fa[cur]].remove(tmp);
                       ch[fa[cur]].insert(pmt);
                   }
                   cur=fa[cur];
               }
               shut[u]^=1;
           }
       }
   

4. 没了，拜拜。