长链剖分学习笔记

重链剖分

重链剖分（heavy path decomposition）¹时，每个内部结点都会选择一个儿子做为自己链上的儿子，我们称为继承儿子（重儿子）。如果一个结点没有被继承，那么它就是一个链顶结点。一棵树剖分过后链的个数是 $\Theta(Leaf)$ 的，其中 $Leaf$ 表示叶子结点的个数。

按照树剖后的顺序先遍历继承儿子，然后遍历其他儿子，那么每条链上的结点的 DFS 序（DFS order）是连续的。这样可以用一个指针数组来模拟二维数组，于是就可以方便地进行一些 DP 转移。

高度

设 $h(u)$ 表示 $u$ 的高度，则

$h(u)=\max_{v\in Son(u)}h(v)+1$

关于高度的性质： $u$ 所在的链长度至少为 $h(u)$ 。

注意区分深度： $dep(u)=dep(F_u)+1$ 。

长链剖分（long path decomposition）指将高度最高的儿子结点作为继承儿子的一种剖分。

形式化地，长链剖分中每个内部结点选择的是其儿子中高度最大的点作为继承结点，设其为 $R_u$ 。

对于子树合并类的信息，在 DFS 的过程中对于每个结点 $u$ ，如果

结点 $u$ 维护的信息量是 $O(h(u))$ 的。
$u$ 可 $O(1)$ 继承 $R_u$ 的信息。
合并两个大小分别为 $x, y$ 的信息的复杂度可以做到 $\min(x, y)$ 。

那么我们可以利用长链剖分做 $O(n)$ 离线计算每个结点的信息。具体方法是 $u$ 继承 $R_u$ 的信息，然后合并其他儿子的信息。复杂度可表示为

$\sum_{u\in T} \sum_{v\in \text{son}(u), v\ne R_u} h(v)$

$h(v)$ 可以理解为是 $v$ 的长链之一。由于 $v\ne R_u$ ，因此 $v$ 本身是轻儿子，也就是说 $v$ 是链顶。因此上述和式本质上就是所有树链的长度和，显然是 $O(n)$ 的。

k 级祖先

给一棵 $n$ 度有根树， $q$ 次询问点 $x$ 的 $k$ 级祖先。

这题可以容易地 $O(n)-O(n)$ 、 $O(n\log_2n)-O(\log_2n)$ 、 $O(n\sqrt{n})-O(\sqrt{n})$ 来做。考虑长链剖分。

首先我们倍增求出 $f(u,j)$ 表示 $u$ 的 $2^j$ 级祖先。另外，对于每个链顶结点 $u$ ，我们预处理出 $u$ 的前 $h(u)$ 级祖先和 $u$ 这条链上的结点序列。

则我们先求出一个最大的 $j$ 使得 $2^j\le k$ 。设 $u'=f(u,j),k'=k-2^j$ ，那么我们要求的就是 $u'$ 的 $k'$ 级祖先。

由于 $h(u')\ge 2^j>k'$ ，因此 $u'$ 的 $k'$ 级祖先要么在 $u'$ 所在的链上，要么在 $u'$ 所在链的链顶结点的祖先序列上。两者都可以 $O(1)$ 查询。因此分类讨论一下即可 $O(1)$ 查询 $k$ 级祖先。

时间复杂度 $O(n\log_2n)-O(1)$ 。

代码

Cookies

有根树。设 $d(u)$ 表示一个序列， $d(u,j)$ 表示在 $u$ 的子树中与 $u$ 距离为 $j$ 的点的个数。对于每个 $u$ 询问 $d(u)$ 中最大值出现第一次的下标。

这题显然可以启发式合并。我们考虑长链剖分。

容易发现 $d(u)$ 的长度为 $h(u)$ 。考虑 $d(u)$ 继承自 $d(R_u)$ 。则显然有

$d(u,i+1)\gets d(R_u,i)\\ d(u,0)\gets 1$

然后我们遍历 $u$ 的非继承儿子 $v$ ，把这些儿子的序列贡献到 $d(u)$ 上：

$d(u,i+1)\gets d(v,i)$

这样就求出了 $d(u)$ 。然后在贡献和继承的时候顺便更新最大值即可，这样复杂度就是遍历非 $R_u$ 之外的结点的复杂度，因此总复杂度 $O(n)$ 。使用 deque 实现，支持在前端插入一个数和随机访问内存，实现起来方便。（只要不遍历长链，复杂度就是对的）

模板，放出核心代码

deque<int> *d[N];
long long ans;

int dep[N],hgh[N];
int a[N],b[N];
void dfs1(int u,int p){
    dep[u]=dep[p]+1;
    hgh[u]=1;
    FORe(i,u,v)if(v!=p)dfs1(v,u),hgh[u]=max(hgh[u],hgh[v]+1);
}
void dfs2(int u,int p){
    int mx=0,son=-1;
    FORe(i,u,v)if(v!=p&&hgh[v]>mx)mx=hgh[v],son=v;
    if(son==-1){
        d[u]=new deque<int>;
        d[u]->pb(1);
        a[u]=0,b[u]=1;
        return;
    }
    dfs2(son,u);
    FORe(i,u,v)if(v!=p&&v!=son)dfs2(v,u);
    // 继承 son
    d[u]=d[son];
    d[u]->push_front(1);
    a[u]=0,b[u]=1;
    if(b[son]>b[u])b[u]=b[son],a[u]=a[son]+1;
    else if(b[son]==b[u])a[u]=min(a[u],a[son]+1);
    // 合并其他儿子的答案
    FORe(i,u,v){
        if(v==p||v==son)continue;
        int lim=(int)d[v]->size()-1;
        int mx2=0,ans=-1;
        FOR(i,0,lim){
            (*d[u])[i+1]+=(*d[v])[i];
            if((*d[u])[i+1]>mx2)mx2=(*d[u])[i+1],ans=i+1;
        }
        if(mx2>b[u])b[u]=mx2,a[u]=ans;
        else if(mx2==b[u])a[u]=min(a[u],ans);
        delete(d[v]);
    }
}

完整代码

谈笑风生

考虑长链剖分。设 $f(u,i)$ 表示子树 $u$ 内与 $u$ 距离为 $i$ 的结点的子树大小减 1 的和：

$f(u,i)=\sum_{v\in T_u,dep(u)+i=dep(v)}S(v)-1$

则分两种情况讨论：

$b$ 是 $a$ 的祖先，则方案数为 $\min(dep(a)-1,k)(S(a)-1)$ ；
$a$ 是 $b$ 的祖先，则方案数为 $\sum_{i=1}^{\min(k,h(a)-1)}f(u,i)$ 。

在继承的时候

$f(u,i+1)\gets f(R_u,i)\\ f(u,0)\gets S(u)-1$

在贡献的时候

$f(u,i+1)\gets f(v,i)$

考虑到我们询问的时候是一个区间和的形式，因此把 $f(u)$ 做后缀和处理即可。这样可以 $O(1)$ 计算询问，也可以 $O(1)$ 转移，复杂度 $O(n)$ 。

这是指针版的写法，感觉更好用：

long long BIN[N],lb;
long long *f[N];

long long ans[N];
int hgh[N],dep[N],sz[N];
vector< pair<int,int> > qry[N];

void dfs1(int u,int p){
    hgh[u]=1,dep[u]=dep[p]+1,sz[u]=1;
    FORe(i,u,v)if(v!=p)dfs1(v,u),sz[u]+=sz[v],hgh[u]=max(hgh[u],hgh[v]+1);
}
void dfs2(int u,int p){
    ++lb;
    int mx=0,son=-1;
    FORe(i,u,v)if(v!=p&&hgh[v]>mx)mx=hgh[v],son=v;
    if(son==-1){
        f[u]=BIN+lb;// 指针赋值
        f[u][0]=sz[u]-1;
        return;
    }
    dfs2(son,u);
    FORe(i,u,v)if(v!=p&&v!=son)dfs2(v,u);

    f[u]=f[son]-1;
    f[u][0]=sz[u]-1+f[u][1];// 后缀和

    FORe(i,u,v){
        if(v==p||v==son)continue;
        FOR(i,0,hgh[v]-1)f[u][i+1]+=f[v][i];
        f[u][0]+=f[v][0];// 后缀和
    }
    // 处理询问
    for(pii p:qry[u]){
        int id=p.fi,k=p.se;
        ans[id]+=1ll*min(dep[u]-1,k)*(sz[u]-1);
        ans[id]+=f[u][1]-(k+1>=hgh[u]?0:f[u][k+1]);
    }
}