静态 Top Tree 小记

· · 个人记录

定义簇（cluster）为一个三元组 C=(u,v,E)。

称 u,v 为 C 的两个界点，E 为簇 C 的边集，u\to v 为 C 的簇路径。

定义合并两个簇的操作 \mathrm{Rake}(C_1,C_2)。

形式化的定义：对于两个满足 u_1=u_2 的簇 C_1,C_2，我们删去点 v_2，合并成一个簇 C'=(u_1,v_1,E_1\cup E_2)。

定义合并两个簇的操作 \mathrm{Compress}(C_1,C_2)。

形式化的定义：对于两个满足 u_2=v_1 的簇 C_1,C_2，我们删去点 u_2/v_1，合并成一个簇 C'=(u_1,v_2,E_1\cup E_2)。

初始的时候我们有 n-1 个簇。我们可以将这 n-1 个簇合并成一个大簇。如果以簇为点，合并过程为边（C' 是 C_1,C_2 的父亲节点），会形成一棵树。这棵树就被称为 Top Tree。

随意造一棵 Top Tree 是容易的：我们可以每次选一个一度点进行 Rake，选一个二度点进行 Compress，直到只剩下两个节点。

然而这样 Top Tree 的高度可能会达到 \mathcal O(n)，没有什么性质。

我们考虑重链剖分，按照如下方式建立 Top Tree：

一个 naive 的想法是，对于 Rake 序列和 Compress 序列的部分，每次都选择中点分治，这样容易证明树高是 \mathcal O(\log ^2 n) 的。

更优的方法是效仿全局平衡二叉树，选择带权的中点。具体来说，Rake 时，认为重儿子的权重为 1，轻儿子的权重为子树大小；Compress 时，认为每个点的权重是所有轻儿子子树大小之和。

这样建出的 Top Tree 树高是 \mathcal O(\log n) 的。

由于查询的时候我们可能会用到每个点所在的簇，因此我们可以在合并过程中存下来，点 u 在哪个簇的合并时被删除了，记为 low_u。

一个还算简洁的建树实现：

#define _RAKE 0
#define _COMPRESS 1
struct Cluster{
    ll u,v,ls,rs,id,fa;
    bool typ;
    Cdat d;
}C[N];
void Rake(Cluster&a,Cluster&b,Cluster&c){
    c.u=a.u,c.v=a.v,c.ls=a.id,c.rs=b.id,a.fa=b.fa=c.id,c.typ=_RAKE;
    c.d=Rakeup(a.d,b.d),low[b.v]=c.id;
}
void Compress(Cluster&a,Cluster&b,Cluster&c){
    c.u=a.u,c.v=b.v,c.ls=a.id,c.rs=b.id,a.fa=b.fa=c.id,c.typ=_COMPRESS;
    c.d=Compressup(a.d,b.d),low[a.v]=c.id;
}
ll fa[N],sz[N],top[N],son[N],tC;
ll dfn[N],ord[N],tim,ed[N];
ll L,pt[N],psum[N],clu[N];
void dfs1(ll x,ll f){
    fa[x]=f,sz[x]=1;
    if(f)to[x].erase(find(to[x].begin(),to[x].end(),f));
    for(ll y:to[x]){
        dfs1(y,x);
        sz[x]+=sz[y];
        if(sz[y]>sz[son[x]])son[x]=y;
        tC++,C[tC]={x,y,0,0,tC,0,0,eps},clu[y]=tC;
    }
}
void dfs2(ll x,ll t){
    top[x]=t,dfn[x]=++tim,ord[tim]=x,ed[t]=x;
    if(!son[x])return ;
    dfs2(son[x],t);
    for(ll y:to[x]){
        if(y!=son[x])dfs2(y,y);
    }
}
ll Build(ll l,ll r,bool op){
    if(l==r)return clu[pt[l]];
    ll ql=l,qr=r-1,pos=l;
    while(ql<=qr){
        ll mid=(ql+qr)>>1;
        if((psum[mid]-psum[l-1])*2<=psum[r]-psum[l-1])pos=mid,ql=mid+1;
        else qr=mid-1;
    }
    ll ls=Build(l,pos,op),rs=Build(pos+1,r,op);
    tC++,C[tC].id=tC;
    if(op==_RAKE)Rake(C[ls],C[rs],C[tC]);
    else Compress(C[ls],C[rs],C[tC]);
    return tC;
}
void dfs3(ll x){
    rep(i,dfn[x],dfn[ed[x]]){
        ll u=ord[i];
        for(ll v:to[u]){
            if(v!=son[u])dfs3(v);
        }
        L=0;
        for(ll v:to[u]){
            if(v!=son[u])pt[++L]=v,psum[L]=sz[v];
        }
        if(son[u]){
            pt[++L]=son[u],psum[L]=1;
            reverse(pt+1,pt+L+1);
            reverse(psum+1,psum+L+1);
            rep(j,1,L)psum[j]+=psum[j-1];
            clu[son[u]]=Build(1,L,_RAKE);
        }
    }
    L=0;
    rep(i,dfn[x],dfn[ed[x]]){
        ll u=ord[i];
        pt[++L]=u,psum[L]=sz[u]-sz[son[u]];
    }
    rep(i,1,L)psum[i]+=psum[i-1];
    clu[x]=Build(1+(x==1),L,_COMPRESS);
}

这里 Compressup 和 Rakeup 就是合并两个簇信息的函数，因使用场景而异。

注意根节点是没有向上的簇的，所以合并时要特殊处理。

接下来是一些使用场景和例题。

加强到任意删点 / 加点，强制在线。

我们考虑对于每个簇维护一些信息。首先显然需要维护簇路径的长度，以及簇内的最短路径。

考虑合并两个簇的时候，肯定会出现跨簇的路径，这些路径可能成为新的答案。因此我们还需要维护簇内的点到 u 和 v 的最短路径。

注意这里由于我们维护的是点信息，所以在合并的时候，会加入那个被删除的点。因此维护信息的时候，我们不维护界点的信息，避免重复计数。

那么合并是容易的，做少量分类讨论即可。最后查询的时候还需要考虑把两个界点加回去。

submission

要求我们 \mathcal O(n\log n) 次信息合并预处理，1 次信息合并查询。

仔细观察会发现这个 R 操作和 C 操作其实就是 Rake 和 Compress，这启发我们建立 Toptree。

考虑建出 Toptree，那么我们思考如何做查询。首先找到包含 (fa_u,u) 这条边的最大簇，满足直径 \le d。那么 (u,d) 这个邻域显然包含这个簇中所有的边。接下来只需要考虑这个簇的两个界点 x,y，从 x,y 往外延申直到距离为 d。

走出去的这两段距离不会超过两个簇的直径，否则我们一开始会找到合并起来的这个更大的簇。因此我们要做的就是预处理出 g_{u,0/1,i} 表示簇 u 的上 / 下界点往外走 i 步的信息并。

为了计算 g，我们显然需要先处理出 f_{u,0/1,i} 表示簇内走 i 步的信息并。发现这些合并都是容易分 Rake / Compress 处理的，并且数组总长度不会超过 \mathcal O(n\log n)，即所有子树大小的和，因此问题解决。

submission