「算法笔记」长链剖分

一、长链剖分

长链剖分本质上就是另外一种链剖分方式。

对于每一个节点：

定义 重子节点 表示其子节点中子树 深度最大 的子节点。如果有多个子树深度最大的子节点，取其一。如果没有子节点，就无重子节点。
定义 轻子节点 表示剩余的子节点。
从这个节点到重子节点的边为重边。到其他轻子节点的边为轻边。
若干条首尾衔接的重边构成长链。把落单的节点也当作长链，那么整棵树就被剖分成若干条互不相交的长链。

树上每个节点都属于且仅属于一条长链。长链剖分实现方式和重链剖分类似。

void dfs1(int x,int fa){
    dep[x]=dep[fa]+1,mx[x]=dep[x],f[x]=fa;    //dep(x) 表示节点 x 在树上的深度，f(x) 表示节点 x 在树上的父亲，mx(x) 表示节点 x 子树中的最大深度 
    for(int i=hd[x];i;i=nxt[i]){
        int y=to[i];
        if(y==fa) continue;
        dfs1(y,x);
        if(mx[y]>mx[son[x]]) son[x]=y,mx[x]=mx[y];    //son(x) 表示节点 x 的重儿子 
    }
}
void dfs2(int x,int topf){
    top[x]=topf,len[x]=mx[x]-dep[top[x]]+1;    //top(x) 表示节点 x 所在长链的顶部结点（深度最小） ，len(x) 表示节点 x 所在长链的长度 
    if(son[x]) dfs2(son[x],topf);    //优先对重儿子进行 DFS 
    for(int i=hd[x];i;i=nxt[i]){
        int y=to[i];
        if(y!=f[x]&&y!=son[x]) dfs2(y,y);
    } 
}

二、一些性质

性质一：对树长链剖分后，树上所有长链的长度和为 (mathcal{O(n)})。

因为每个点仅属于一条长链，只会被计算一次，所以长链长度的总和为 (mathcal{O(n)})。

性质二：任意一个节点 (x) 的 (k) 级祖先 (y) 所在长链的长度一定大于等于 (k)。

如果 (y) 所在的长链的长度小于 (k)，那么它所在的链一定不是长链，因为 (y o x) 这条链显然更优，那么 (y) 所在的长链长度至少为 (k)，性质成立；反之，(y) 所在长链的长度大于等于 (k)，性质成立。

性质三：一个节点跳跃长链到根节点，跳跃的次数最多为 (mathcal{O(sqrt{n})})。

如果一个节点 (x) 从一条长链跳到了另外一条长链上，那么跳跃到的这条长链的长度不会小于之前的长链长度。最坏情况下，链长分别为 (1,2,cdots,sqrt{n})，也就是最多跳跃 (sqrt{n}) 次。

三、树上 k 级祖先

注：在接下来的描述中，默认时间复杂度标记方式为 (mathcal{O}()数据预处理()-mathcal{O}()单次询问())。

树上一个节点的 (k) 级祖先可以采用传统的倍增方法求，时间复杂度为 (mathcal{O(nlog n)}−mathcal{O(log n)})。
也可以直接重链剖分后，在重链上跳，时间复杂度为 (mathcal{O(n)}−mathcal{O(log n)})。

有没有更快的方法呢？

考虑对整棵树进行 长链剖分，并预处理出：

倍增求出每一个节点的 (2^i) 级祖先。
对于每条长链的链顶节点，设其所在的长链长度为 (d)，求出这个点向上的 (d) 个祖先和向下的 (d) 个儿子。

假设我们找到了询问节点的 (2^i) 级祖先满足 (2^i<k<2^{i+1})。我们先跳 (2^i) 级，还需跳 (k-2^i) 级。显然 (k-2^i<2^i)。当前的 (x) 在原先 (x) 的 (2^i) 级祖先的位置上。

根据长链剖分的性质，「任意一个节点 (x) 的 (k) 级祖先所在长链的长度一定大于等于 (k)」，所以 (k-2^i<2^ileq d)（其中 (d) 为 当前的 (x) 所在长链的长度）。

由于 (k-2^i<d)，所以可以先将 (x) 跳到 (x) 所在长链的链顶节点上。若之后剩下的级数为正，则利用向上的数组求出答案，否则利用向下的数组求出答案，向上和向下的数组已经通过预处理求出了。

时间复杂度：(mathcal{O}(nlog n)-mathcal{O}(1))。

//Luogu P5903 
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e5+5;
int n,q,x,k,rt,cnt,hd[N],to[N<<1],nxt[N<<1],f[N][30],dep[N],mx[N],son[N],top[N],len[N],res,ans;
unsigned s;
vector<int>v1[N],v2[N];    //每条长链的链顶节点 x 向上的 len(x) 个祖先和向下的 len(x) 个儿子。其中 len(x) 表示节点 x 所在长链的长度。  
unsigned get(unsigned x){    //数据生成，见题目 
    x^=x<<13,x^=x>>17,x^=x<<5;
    return s=x;
}
void add(int x,int y){
    to[++cnt]=y,nxt[cnt]=hd[x],hd[x]=cnt;
}
void dfs1(int x,int fa){
    dep[x]=dep[fa]+1,mx[x]=dep[x];
    for(int i=0;i<=19;i++)
        f[x][i+1]=f[f[x][i]][i]; 
    for(int i=hd[x];i;i=nxt[i]){
        int y=to[i];
        if(y==fa) continue;
        f[y][0]=x,dfs1(y,x);
        if(mx[y]>mx[son[x]]) son[x]=y,mx[x]=mx[y];
    }
}
void dfs2(int x,int topf){
    top[x]=topf,len[x]=mx[x]-dep[top[x]]+1;
    if(son[x]) dfs2(son[x],topf);
    for(int i=hd[x];i;i=nxt[i]){
        int y=to[i];
        if(y!=f[x][0]&&y!=son[x]) dfs2(y,y);
    }
}
int query(int x,int k){
    if(!k) return x;
    int t=log(k)/log(2);    //2^t<k<2^{t+1} 
    x=f[x][t],k-=(1<<t),k-=dep[x]-dep[top[x]],x=top[x];
    if(!k) return x;
    return k>0?v1[x][k-1]:v2[x][-k-1];
}
signed main(){
    scanf("%lld%lld%u",&n,&q,&s);
    for(int i=1;i<=n;i++){
        scanf("%lld",&x);
        if(!x) rt=i;
        else add(i,x),add(x,i); 
    }
    dfs1(rt,0),dfs2(rt,rt);
    for(int i=1;i<=n;i++){
        if(i!=top[i]) continue;
        for(int j=1,x=i;j<=len[i];j++)
            x=f[x][0],v1[i].push_back(x);
        for(int j=1,x=i;j<=len[i];j++)
            x=son[x],v2[i].push_back(x);
    }
    for(int i=1;i<=q;i++){
        x=(get(s)^res)%n+1,k=(get(s)^res)%dep[x];    //按题目要求生成询问 
        res=query(x,k),ans^=i*res;    //res 为当前询问的答案 
    }
    printf("%lld
",ans);
    return 0;
}

四、长链剖分优化 DP

1. CF1009F Dominant Indices

题目大意：给定一棵以 (1) 为根，(n) 个节点的树。设 (d(u,x)) 为 (u) 子树中到 (u) 距离为 (x) 的节点数。

对于每个点，求一个最小的 (k)，使得 (d(u,k)) 最大。(1leq nleq 10^6)。

Solution：

令 (f_{i,j}) 表示节点 (i) 的子树内，到 (i) 距离为 (j) 的节点数量。

显然 (f_{u,0}=1,f_{u,i}=sumlimits_{vin son(u)} f_{v,i-1})。这样直接暴力转移的时间复杂度为 (mathcal{O}(n^2))。

考虑用长链剖分优化。在维护信息的过程中，先 (mathcal{O}(1)) 继承重儿子的信息，再暴力合并其余轻儿子的信息。

具体地，对于每一个节点 (u)，先对它的重儿子 (v) 做 DP，转移时直接继承重儿子的 DP 数组和答案。当然观察 DP 式子可以发现这里需要错一位，因为 (v) 子树内「到 (v) 距离为 (i) 的节点」与 (u) 的距离为 (i+1)。所以可以在继承后，将当前节点的 DP 数组前面插入一个元素 (1)（即 (f_{u,0}=1)），表示当前节点。接下来对它的轻儿子 做 DP，将所有轻儿子的 DP 数组暴力和当前节点的 DP 数组合并。

因为每个点仅属于一条长链，且一条长链只会在链顶位置作为轻儿子暴力合并一次，所以复杂度线性。

在「(mathcal{O}(1)) 继承重儿子的信息」这点上有不同的实现方式，一个巧妙的方法是利用指针实现，这里使用 vector 实现。

#include<bits/stdc++.h>
#define int long long
using namespace std; 
const int N=1e6+5;
int n,x,y,cnt,hd[N],to[N<<1],nxt[N<<1],len[N],son[N],ans[N];
vector<int>f[N];    //这里的 vector 是倒序存储的，因为要在继承重儿子的信息后，要将当前节点的 DP 数组最前面插入一个元素，而 push_back 的复杂度优于 pop_front，倒序存储就可以直接使用 push_back 
void add(int x,int y){
    to[++cnt]=y,nxt[cnt]=hd[x],hd[x]=cnt;
}
int get(int x,int id){    //由于 vector 是倒序存储的，此处将 vector 正序存储的位置转化为倒序存储的位置 
    return len[x]-id-1;
}
void dfs1(int x,int fa){
    for(int i=hd[x];i;i=nxt[i]){
        int y=to[i];
        if(y==fa) continue;
        dfs1(y,x);
        if(len[y]>len[son[x]]) son[x]=y;
    }
    len[x]=len[son[x]]+1;
}
void dfs2(int x,int fa){
    if(son[x]) dfs2(son[x],x),swap(f[x],f[son[x]]),ans[x]=ans[son[x]]+1;    //继承重儿子的信息。这里的继承直接用 swap 而不是复制，swap 在时间和空间上都更优（swap 交换 vector 的时间复杂度为 O(1)）。 
    f[x].push_back(1);    //push_back 的复杂度优于 pop_front
    for(int i=hd[x];i;i=nxt[i]){
        int y=to[i];
        if(y==fa||y==son[x]) continue;
        dfs2(y,x);
        for(int j=1;j<=len[y];j++){
            f[x][get(x,j)]+=f[y][get(y,j-1)];    //暴力合并轻儿子的信息 
            if(f[x][get(x,j)]>f[x][get(x,ans[x])]||(f[x][get(x,j)]==f[x][get(x,ans[x])]&&j<ans[x])) ans[x]=j;    //更新答案
        }
    }
    if(f[x][get(x,ans[x])]==1) ans[x]=0;    //f[x][0]=1,f[x][ans[x]]=1，0 显然更优
}
signed main(){
    scanf("%lld",&n);
    for(int i=1;i<n;i++){
        scanf("%lld%lld",&x,&y);
        add(x,y),add(y,x);
    }
    dfs1(1,0),dfs2(1,0);
    for(int i=1;i<=n;i++)
        printf("%lld
",ans[i]);
    return 0;
}

附指针版本：我们只对每一条长链的顶端节点申请内存，让一条长链上的所有节点公用一片空间。具体地，对节点 (u) 申请了内存之后，设 (v) 是 (u) 的重儿子，我们就把 (f_u) 数组的起点（的指针）加一作为 (f_v) 数组的起点（的指针）。具体见代码。

#include<bits/stdc++.h>
#define int long long
using namespace std; 
const int N=1e6+5;
int n,x,y,cnt,hd[N],to[N<<1],nxt[N<<1],len[N],son[N],ans[N],*f[N],tmp[N],*id=tmp;
void add(int x,int y){
    to[++cnt]=y,nxt[cnt]=hd[x],hd[x]=cnt;
}
void dfs1(int x,int fa){
    for(int i=hd[x];i;i=nxt[i]){
        int y=to[i];
        if(y==fa) continue;
        dfs1(y,x);
        if(len[y]>len[son[x]]) son[x]=y;
    }
    len[x]=len[son[x]]+1;
}
void dfs2(int x,int fa){ 
    f[x][0]=1;
    if(son[x]) f[son[x]]=f[x]+1,dfs2(son[x],x),ans[x]=ans[son[x]]+1;    //继承重儿子的信息。f[son[x]]=f[x]+1: 共享内存，这样之后，f[son[x]][i] 会被存到 f[x][i+1]  
    for(int i=hd[x];i;i=nxt[i]){
        int y=to[i];
        if(y==fa||y==son[x]) continue;
        f[y]=id,id+=len[y],dfs2(y,x);    //分配内存。为 y 节点申请内存，大小等于以 y 为顶端的长链的长度。申请的内存要能装下一条长链。 
        for(int j=1;j<=len[y];j++){
            f[x][j]+=f[y][j-1];    //暴力合并轻儿子的信息 
            if(f[x][j]>f[x][ans[x]]||(f[x][j]==f[x][ans[x]]&&j<ans[x])) ans[x]=j;    //更新答案 
        }
    }
    if(f[x][ans[x]]==1) ans[x]=0;    //f[x][0]=1,f[x][ans[x]]=1，0 显然更优 
}
signed main(){
    scanf("%lld",&n);
    for(int i=1;i<n;i++){
        scanf("%lld%lld",&x,&y);
        add(x,y),add(y,x);
    }
    dfs1(1,0),f[1]=id,id+=len[1],dfs2(1,0);    //在 DP 开始前先为以树根为顶端的长链申请内存 
    for(int i=1;i<=n;i++)
        printf("%lld
",ans[i]);
    return 0;
}

2. BZOJ 4543 [POI2014]Hotel 加强版

题目大意：给定一棵 (n) 个节点的树，在树上选 (3) 个点，要求两两距离相等，求方案数。(1leq nleq 10^5)。

Solution：

令 (f_{u,i}) 表示以 (u) 为根的子树中，距离 (u) 为 (i) 的节点个数。(g_{u,i}) 表示以 (u) 为根的子树中，两个点 (x,y) 到其 ( ext{lca}) 的距离为 (d)，且 ( ext{lca}) 到 (u) 的距离为 (d-i) 的方案数。

转移：(f_{u,i}=sumlimits_{vin son(u)}f_{v,i-1},g_{u,i}=sumlimits_{vin son(u)}g_{v,j+1}+f_{u,i} imes f_{v,i-1})。可以画图理解。

求出了 (f) 和 (g)，那么就能求出答案了（首先令 (ans=sumlimits_{u} g_{u,0})）：

1. 在 (u) 的子树中选两个点，与 (v) 中的点拼：(ans=ans+g_{u,i} imes f_{v,i-1})。
2. 在 (v) 的子树中选两个点，与 (u) 中的点拼：(ans=ans+f_{u,i} imes g_{v,i+1})。

如图，以第一种情况为例（第二种情况同理）。

「算法笔记」长链剖分

暴力转移的时间复杂度为 (mathcal{O}(n^2))。然后用长链剖分优化成 (mathcal{O}(n)) 即可。

同样是继承重儿子的信息，再暴力合并其余轻儿子的信息。

由于 (g) 数组转移的特殊，下标的变化很玄学，使用 vector 的写法细节较多，使用指针分配内存的方法就可以减少细节量。

把 (f_u) 数组的起点（的指针）加一作为 (f_v) 数组的起点（的指针），(g_u) 数组的起点（的指针）减一作为 (g_v) 数组的起点（的指针）。(f_{v}=f_{u}+1,g_{v}=g_{u}-1)。

发现 (g) 的更新是反过来的，为了避免出错可以 多开点空间。顺便放一个 Dls 写的非 vector 非指针的写法。

#include<bits/stdc++.h>
#define int long long
using namespace std; 
const int N=1e5+5;
int n,x,y,cnt,hd[N],to[N<<1],nxt[N<<1],len[N],son[N],*f[N],*g[N],tmp[N<<2],*id=tmp,ans;
void add(int x,int y){
    to[++cnt]=y,nxt[cnt]=hd[x],hd[x]=cnt;
}
void dfs1(int x,int fa){
    for(int i=hd[x];i;i=nxt[i]){
        int y=to[i];
        if(y==fa) continue;
        dfs1(y,x);
        if(len[y]>len[son[x]]) son[x]=y;
    }
    len[x]=len[son[x]]+1;
}
void dfs2(int x,int fa){
    if(son[x]) f[son[x]]=f[x]+1,g[son[x]]=g[x]-1,dfs2(son[x],x);    //继承重儿子的信息 
    f[x][0]=1,ans+=g[x][0]; 
    for(int i=hd[x];i;i=nxt[i]){
        int y=to[i];
        if(y==fa||y==son[x]) continue;
        f[y]=id,id+=len[y]<<1,g[y]=id,id+=len[y]<<1,dfs2(y,x);
        for(int j=1;j<=len[y];j++){     //暴力合并轻儿子的信息 
            ans+=g[x][j]*f[y][j-1]+f[x][j-1]*g[y][j];
            g[x][j]+=f[x][j]*f[y][j-1];
        } 
        for(int j=1;j<=len[y];j++)
            f[x][j]+=f[y][j-1],g[x][j-1]+=g[y][j];
    }
}
signed main(){
    scanf("%lld",&n);
    for(int i=1;i<n;i++){
        scanf("%lld%lld",&x,&y);
        add(x,y),add(y,x);
    }
    dfs1(1,0),f[1]=id,id+=len[1]<<1,g[1]=id,id+=len[1]<<1,dfs2(1,0);
    printf("%lld
",ans);
    return 0;
}

3. 一些总结

长链剖分可以把维护子树中 只与深度有关 的信息优化到线性。

长链剖分优化 DP 的实现方式就是，长链剖分后，在维护信息的过程中，先 (mathcal{O}(1)) 继承重儿子的信息，再暴力合并其余轻儿子的信息。

顺便再放一些题：

Luogu P3899 [湖南集训]谈笑风生
Luogu P4292 [WC2010]重建计划

五、维护贪心

BZOJ 3252 攻略

题目大意：给定一棵 (n) 个节点的树，每个点有点权。要求选定 (k) 个叶子节点，使得根节点到这 (k) 个叶子节点的所有路径所覆盖的点权和最大。每个点的权值只能被计算一次。

(nleq 2 imes 10^5,1leq wleq 2^{31}-1)，其中 (w) 表示点权。

Solution：

每次选取一条权值之和最大的路径，然后将路径上所有点的权值清零。

用长链剖分来实现这个贪心。

考虑带权的长链剖分，剖出的链取前 (k) 条加起来即可。时间复杂度 (mathcal{O}(nlog n))。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+5;
int n,k,x,y,a[N],tot,b[N],cnt,hd[N],to[N<<1],nxt[N<<1],len[N],son[N],f[N],top[N],ans;
void add(int x,int y){
    to[++cnt]=y,nxt[cnt]=hd[x],hd[x]=cnt;
}
void dfs1(int x,int fa){
    for(int i=hd[x];i;i=nxt[i]){
        int y=to[i];
        if(y==fa) continue;
        f[y]=x,dfs1(y,x);
        if(len[y]>len[son[x]]) son[x]=y;
    }
    len[x]=len[son[x]]+a[x];
}
void dfs2(int x,int topf){
    top[x]=topf;
    if(son[x]) dfs2(son[x],topf);
    for(int i=hd[x];i;i=nxt[i]){
        int y=to[i];
        if(y!=f[x]&&y!=son[x]) dfs2(y,y);
    }
}
signed main(){
    scanf("%lld%lld",&n,&k);
    for(int i=1;i<=n;i++)
        scanf("%lld",&a[i]);
    for(int i=1;i<n;i++){
        scanf("%lld%lld",&x,&y);
        add(x,y),add(y,x);
    }
    dfs1(1,0),dfs2(1,1);
    for(int i=1;i<=n;i++)
        if(top[i]==i) b[++tot]=len[i];
    sort(b+1,b+1+tot,greater<int>());
    for(int i=1;i<=k;i++) ans+=b[i];    //取前 k 大 
    printf("%lld
",ans);
    return 0;
}