点分树一点都不会啊（还是太菜了）

点分树就是我们点分治构成的新树。满足深度很小。

然后我们就可以在上面瞎维护东西了。

三个大根堆：

\(C[u]\)里装的是点分树中u的子树所有点到点分树中u的父亲的距离。

\(B[u]\)里装的是点分树中u的所有儿子的C的最大值。

\(A\)里装的是所有\(B\)的最大值与次大值之和。

\(A\)的堆顶就是答案。

（我一开始一直以为两个堆就行，对第三个对表示疑惑，又懒得深入想，一直翻题解。千万不能犯懒不想啊）

我们找答案可以快速找到。问题是怎么维护？

因为我们是点分树，深度小，可以直接一个一个跳到根暴力修改维护。具体一些就是设删的点为\(x\)，跳到一个点\(u\)把\(x\)的贡献从\(C[u]\)中删掉，然后重新跟新\(B[u]\)和\(A\)。

至此本题得到解决，就是我代码常数太大。

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;const int N=200100;struct que{ priority_queue
          
            x,y; inline void push(int a){x.push(a);} inline void del(int a){y.push(a);} inline int top(){while(y.size()&&x.top()==y.top())x.pop(),y.pop();return x.top();} inline int size(){return x.size()-y.size();} inline void pop(){while(y.size()&&x.top()==y.top())x.pop(),y.pop();x.pop();} inline int sectop(){int a=top();pop();int b=top();push(a);return b;}}A,B[N],C[N];int cnt,head[N];int light[N],tot,n,m;int root,size[N],g[N],vis[N],all,f[N];int dep[N],mn[N*2][24],num,dfn[N];int Log[N];struct edge{ int to,nxt;}e[N*2];inline void add_edge(int u,int v){ cnt++; e[cnt].nxt=head[u]; e[cnt].to=v; head[u]=cnt;}inline void dfs(int u,int f){ dfn[u]=++num; dep[u]=dep[f]+1; mn[num][0]=dep[u]; for(int i=head[u];i;i=e[i].nxt){ int v=e[i].to; if(v==f)continue; dfs(v,u); mn[++num][0]=dep[u]; }}inline void getroot(int u,int f){ g[u]=0;size[u]=1; for(int i=head[u];i;i=e[i].nxt){ int v=e[i].to; if(v==f||vis[v])continue; getroot(v,u); g[u]=max(g[u],size[v]); size[u]+=size[v]; } g[u]=max(g[u],all-size[u]); if(g[u]
           
            b)swap(a,b); int len=Log[b-a+1]; return min(mn[a][len],mn[b-(1<
            
             =2)A.push(B[x].top()+B[x].sectop());}inline void dela(int x){ if(B[x].size()>=2)A.del(B[x].top()+B[x].sectop());}inline void build(int u,int ff){ f[u]=ff;vis[u]=1; B[u].push(0); work(u,0); for(int i=head[u];i;i=e[i].nxt){ int v=e[i].to; if(vis[v])continue; root=0,all=size[v]; getroot(v,0); v=root; build(root,u); B[u].push(C[v].top()); } pusha(u);}inline void on(int x){ dela(x); B[x].del(0); pusha(x); for(int i=x;f[i];i=f[i]){ dela(f[i]); B[f[i]].del(C[i].top()); C[i].del(dis(x,f[i])); if(C[i].size())B[f[i]].push(C[i].top()); pusha(f[i]); }}inline void off(int x){ dela(x); B[x].push(0); pusha(x); for(int i=x;f[i];i=f[i]){ dela(f[i]); if(C[i].size())B[f[i]].del(C[i].top()); C[i].push(dis(x,f[i])); B[f[i]].push(C[i].top()); pusha(f[i]); }}void prework(){ for(int j=1;j<=Log[num];j++) for(int i=1;i+(1<
             
              <=num;i++) mn[i][j]=min(mn[i][j-1],mn[i+(1<<(j-1))][j-1]);}inline int read(){ int sum=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){sum=sum*10+ch-'0';ch=getchar();} return sum*f;}int main(){ n=read(); Log[0]=-1;for(int i=1;i<=200000;i++)Log[i]=Log[i>>1]+1; for(int i=1;i