长链剖分记

· · 算法·理论

对于一颗 n 个结点的树，以下无特殊说明时没有边权，有边权时一般非负。所以有边权的情况在无边权的情况下同样适用。仿照重链剖分，考虑以下定义：

长儿子：一个结点的所有儿子中，子树深度最大的儿子。

长链：连续的长儿子组成的链。

使用两次 dfs，第一次处理结点深度、长儿子等信息，第二次处理长链信息、dfn 序等。注意第二次搜索先走长儿子。

预处理可以简单做到 \mathcal{O}(n)。我们还可以观察到一些比较显然的性质：

  1. 所有长链长度之和为 \mathcal{O}(n)。长链之间互不相交。长链的末端是叶子结点。
  2. 对于一个结点 x 的 k 级祖先 y，y 所在长链的长度一定 \ge k。此时 y 一定存在长度 =k 的链，如果这条链不作为长链，则长链长度 >k，否则 =k。
  3. 我们也可以知道，对于同一条祖先链上的长链链头 e_1,e_2 ,\ldots e_k 及其对应的长链长度 L_1,L_2 ,\ldots ,L_k，若 \mathrm{dep}(e_i)<\mathrm{dep}(e_j)，则有 L_i>L_j。有边权时同样成立。
  4. 从任意一个结点 x 开始，不停向上跳长链，最多跳 \mathcal{O}(\sqrt{n}) 次。因为 x 每跳一次长链，x 所在长链的长度最少 +1（这不代表每次跳长链的距离一定会越来越大），又因为长链之间互不相交，所以假如我们跳了 c 次长链，一定有 n \ge \sum _{i=1}^{c}i=\mathcal{O}(c^2)。故 c 的上界是 \mathcal{O}(\sqrt{n})。更加一般的，假如长链剖分的树上有边权，对树进行带权的长链剖分，记边权分别为 w_1,w_2,\ldots ,w_{n-1}，我们可以得到 c 的上界为 \mathcal{O}\left (\sqrt{\sum_{i=1}^{n-1}\limits w_i}\right )，这个和上面的推导方式相同。
  5. 与重链剖分相同，在一条长链上的点 dfn 序连续。
  6. 在边有边权时（意思是深度也带权），长链剖分也可以维护一类贪心。具体而言，如果我们要选出 k 个点，最大化这 k 个点到根路径的并的边权和时，答案为前 k 长的长链之和，此时选择的 k 个点为前 k 长的长链的末端。这个比较容易感性理解。

例题 1

给定一颗 n 个结点的树，有 q 次查询。每次给定 x,k，求 x 的 k 级祖先。

使用树上倍增或重链剖分可以分别做到 \mathcal{O}(n \log n)-\mathcal{O}(\log n) 或 \mathcal{O}(n)-\mathcal{O}(\log n)。

利用长链剖分，我们可以做到 \mathcal{O}(n \log n)-\mathcal{O}(1)。

先进行树上倍增的预处理，处理出每个 x 的 2^c 级祖先。

对于一次询问而言，对于 2^c \le k <2^{c+1}，考虑先让 x 用树上倍增的数组跳 2^c 级祖先，到了 x'。

此时我们还有 k'=k-2^c 级祖先没跳。因为 k<2^{c+1}，所以 k'<2^c。

对于每条长链，若其长度为 l，考虑分别预处理出链头向上前 l 级祖先，链头在链上向下前 l 级孩子。后者可以直接使用 dfn 序在长链上连续的性质。

因为所有长链长度之和为 \mathcal{O}(n)，所以这里预处理的总量是 \mathcal{O}(n)。

因为 k' <2^c，而 x' 是 x 的 2^c 级祖先，所以 x' 所在长链长度 \ge 2^c。根据上面的预处理，我们只需分类讨论 x' 的 k' 级祖先在 x' 所在长链的链头上面还是下面即可。

这样单次查询的时间复杂度就是严格 \mathcal{O}(1) 了。实现有一定量的细节。

#include<bits/stdc++.h> 
#define rd read()
#define gc getchar()
using namespace std;
inline int read(){
    register int x=0,ss=1,s=gc;
    while(!isdigit(s)&&s!='-')s=gc;if(s=='-')ss=-1,s=gc;
    while(isdigit(s))x=(x<<1)+(x<<3)+(s^48),s=gc;
    return ss*x;
}
const int N=500005;
unsigned s;long long out;
inline unsigned get(unsigned x) {
    x^=x<<13,x^=x>>17,x^=x<<5;
    return s=x; 
}
int n,q,rt,cnt;
int dep[N],mx[N],son[N],dfn[N],rev[N],top[N],lg[N],f[20][N];
vector<int> v[N],up[N];
inline void dfs(int x){
    mx[x]=dep[x];
    for(int i:v[x])
        dep[i]=dep[x]+1,dfs(i),
        (mx[i]>mx[son[x]])&&(mx[x]=mx[i],son[x]=i);
}
inline void dfs2(int x,int t){
    dfn[rev[++cnt]=x]=cnt,top[x]=t;
    if(x==t)
        for(int h=x,i=0;i<=mx[x]-dep[x];h=f[0][h],++i)
            up[x].push_back(h);
    if(!son[x])return;dfs2(son[x],t);
    for(int i:v[x])if(i!=son[x])dfs2(i,i);
}
inline int Q(int x,int k){
    if(!k)return x;
    x=f[lg[k]][x],k-=1<<lg[k];
    int t=dep[x]-dep[top[x]];
    if(t<k)return up[top[x]][k-t];
    return rev[dfn[top[x]]+t-k];
}
signed main(){
    n=rd,q=rd,cin>>s;
    for(int i=1;i<=n;++i){
        v[f[0][i]=rd].push_back(i);
        if(!f[0][i])rt=i;
    }
    for(int i=2;i<=n;++i)lg[i]=lg[i>>1]+1;
    for(int i=1;i<=lg[n];++i)
        for(int j=1;j<=n;++j)f[i][j]=f[i-1][f[i-1][j]];
    dep[rt]=1,dfs(rt),dfs2(rt,rt);
    for(int i=1,res=0,x,k;i<=q;++i)
        x=(get(s)^res)%n+1,k=(get(s)^res)%dep[x],
        out^=1ll*i*(res=Q(x,k));
    cout<<out<<'\n';return 0;
}

例题 2

给定一颗 n 个结点的树。对于每个结点，求出其子树中出现次数最多的最小深度。

记 f_{i,j} 为以编号为 i 的结点为根的子树中深度为 j 的结点数。

容易得到 f_{i,j}=\sum \limits _{x \in \mathrm{son}(i)}f_{x,j-1},f_{i,0}=1。

可以直接线段树合并做到时空 \mathcal{O}(n \log n)，考虑优化。

不妨仿照 dsu on tree，在处理 f_{i,j} 时，我们先选择一个儿子的信息继承，然后其他儿子的信息直接暴力加入。

不难发现直接继承长儿子的信息最优，因为长儿子的 j 一维最大。

考虑此时的复杂度。对于一条长链的信息，我们会在长链顶端向父亲合并的时候暴力合并，长链中间都是直接继承。而暴力合并时，子树中的最大深度刚好是长链的长度 l。所以暴力合并的总量是 \mathcal{O}(n)。空间可以动态分配。

故算法的时空复杂度为 \mathcal{O}(n)。

#include<bits/stdc++.h> 
#define rd read()
#define gc getchar()
using namespace std;
inline int read(){
    register int x=0,ss=1,s=gc;
    while(!isdigit(s)&&s!='-')s=gc;if(s=='-')ss=-1,s=gc;
    while(isdigit(s))x=(x<<1)+(x<<3)+(s^48),s=gc;
    return ss*x;
}
const int N=1000005;
int n,mx[N],dep[N],son[N],ans[N],e[N];vector<int> v[N],dp[N];
inline void dfs(int x,int f){
    mx[x]=dep[x];
    for(int i:v[x])if(i!=f)
        dep[i]=dep[x]+1,dfs(i,x),
        (mx[i]>mx[son[x]])&&(mx[x]=mx[i],son[x]=i);
}
inline void sol(int x,int f){
    if(!son[x])return dp[x].push_back(1);
    sol(son[x],x),swap(dp[x],dp[son[x]]);
    dp[x].push_back(1);//实现上为方便追加，将数组倒序了
    e[x]=dp[x].size()-1,ans[x]=ans[son[x]]+1;
    if(dp[x][e[x]-ans[x]]==1)ans[x]=0;
    for(int i:v[x])if(i!=f&&i!=son[x]){
        sol(i,x);
        for(int j=0;j<=e[i];++j)
            dp[x][e[x]-j-1]+=dp[i][e[i]-j],
            (dp[x][e[x]-j-1]>dp[x][e[x]-ans[x]]||
            dp[x][e[x]-j-1]==dp[x][e[x]-ans[x]]&&ans[x]>j+1)&&(ans[x]=j+1);
    }
}
signed main(){
    n=rd;
    for(int i=1,x,y;i<n;++i)
        x=rd,y=rd,
        v[x].push_back(y),
        v[y].push_back(x);
    dfs(1,0),sol(1,0);
    for(int i=1;i<=n;++i)cout<<ans[i]<<'\n';
    return 0;
}

例题 3

给出一棵有 n 个点的树，求有多少组点 (i,j,k) 满足 i,j,k 两两之间的距离都相等。(i,j,k) 与 (i,k,j) 算作同一组。

与弱化版本在三个结点间的路径的交点处计数不同，考虑在三个点 (x,y,z) 的最近公共祖先 \mathrm{LCA}(x,y,z) 处计数。则三个结点的位置情形必然如下图一般：

记录 f_{u,L} 为在以 u 为根的子树中与 u 的距离为 L 的点的数量，而 g_{u,i} 为以 u 为根的子树中满足 \mathrm{LCA}(x,y) 与 u 的距离 c 有 L-c=i 的点对 (x,y) 数。

为什么这样设呢，假如要基于 g 的值统计 z 的数量，我们就需要存下 L 和 c 的值，这样做至少有三维状态，复杂度过高。而且在统计 z 时我们实际上只关心 L-c 的值。

计算 f 就是上一题，考虑依次合并 u 的儿子 y，一个 y 子树中的点对 (x,y) 在传递到 u 时会有 c \gets c+1，即 L-c 减少 1，在加上新的结点与老节点间的贡献，故 g 的转移式为：

g_{u,i}=g_{u,i}+g_{y,i+1}+f_{u,i}f_{y,i-1}

合并的时候再考虑如何利用 f,g 统计答案，新的贡献应该满足至少一个点在 y 的子树中，讨论在 y 的子树中有一个还是两个结点，由定义可知贡献为 \sum \limits _{j}f_{y,j}g_{u,j+1}+f_{u,j+1}g_{y,j}。最后还有 g_{u,0} 的贡献。

直接计算可以做到 \mathcal{O}(n^2)。不难观察到，f,g 的第二维都与深度线性相关。于是考虑使用长链剖分优化转移即可。

复杂度与上题相同，时空均为 \mathcal{O}(n)。第一次用指针，调得十分痛苦。

#include<bits/stdc++.h>
#define int long long
#define rd read()
#define gc pa == pb && (pb = (pa = buf) + fread(buf, 1, 100000, stdin), pa == pb) ? EOF : *pa++
using namespace std;
static char buf[100000], * pa(buf), * pb(buf);
inline int read(){
    register int x=0,ss=1,s=gc;
    while(!isdigit(s)&&s!='-')s=gc;if(s=='-')ss=-1,s=gc;
    while(isdigit(s))x=(x<<1)+(x<<3)+(s^48),s=gc;
    return ss*x;
}
const int N=100005;
int n,ans,mx[N],son[N],dep[N],ln[N];vector<int> v[N];
int *f[N],*g[N],o[N<<2],*p=o;
inline void dfs(int x,int f){
    mx[x]=dep[x]=dep[f]+1;
    for(int i:v[x])if(i!=f){
        dfs(i,x);
        if(mx[i]>mx[son[x]])son[x]=i,mx[x]=mx[i];
    }
    ln[x]=mx[x]-dep[x]+1;
}
inline void sol(int x,int F){
    if(son[x])
        f[son[x]]=f[x]+1,g[son[x]]=g[x]-1,
        sol(son[x],x);
    f[x][0]=1,ans+=g[x][0];
    for(int i:v[x])if(i!=F&&i!=son[x]){
        f[i]=p,p+=ln[i]<<1,g[i]=p,p+=ln[i]<<1,sol(i,x);
        for(int j=0;j<ln[i];++j)
            ans+=f[x][j]*g[i][j+1]+g[x][j+1]*f[i][j];
        for(int j=0;j<ln[i];++j){
            g[x][j+1]+=f[x][j+1]*f[i][j];
            f[x][j+1]+=f[i][j];
            if(j)g[x][j-1]+=g[i][j];
        }
    }
}
signed main(){
    n=rd;
    for(int i=1,x,y;i<n;++i)
        x=rd,y=rd,
        v[x].push_back(y),
        v[y].push_back(x);
    dfs(1,0),f[1]=p,p+=ln[1]<<1,
    g[1]=p,p+=ln[1]<<1,sol(1,0);
    cout<<ans<<'\n';return 0;
}

例题 4

给定一棵 n 个结点的树，边有边权。q 次查询，每次查询给出 x,y，在树上选 y 条路径，求路径之并包含 x 且是连通块时的最大边权之和。

强制在线。

这题神了。

是否包含 x 和边权最大两个条件都会在我们选择到更多边的时候更优。所以选择的路径必然是两个叶子间组成的，考虑每次查询选择 2y 个儿子并将它们相连。

显然的，对于一棵有 k 个叶子的树，我们可以用不超过 \left \lceil \dfrac{k}{2} \right \rceil 条路径将其覆盖。证明可以考虑，通过调整叶子结点间的路径包含到根节点，叶子较少的子树因为叶子全部向上连出去被完全覆盖，然后递归处理叶子较多的儿子的子树，这样一定可以覆盖整棵树。

又观察到，因为包含 x 的最长路径的其中一个端点必然是树直径的其中一个端点，所以我们选择的路径中一定有一条路径的端点是直径端点。

考虑分别令两个直径端点为根，强制选择根，答案取两种情况的最大值，考虑其中一种即可。

选了根后剩下的位置，我们还可以选择 (2y-1) 个叶子，根据上面的性质，我们可以用这 (2y-1) 个叶子间与根的路径包含这 2y 个点组成的虚树。此时树的形态可以直接用 (2y-1) 分别连到根的路径之并得到。

则我们的问题转换为了选 (2y-1) 个叶子，其中至少一个在 x 的子树中，最大化叶子们到根的路径之并的边权和。

假如没有 x 的限制，可以使用带权的长链剖分，然后我们会直接选取前 (2y-1) 长的长链。当有这个限制时，我们考虑在此基础上进行调整，这意味我们需要调整时 x 子树中没有一条边被覆盖。调整后显然我们在 x 的子树中选择了 x 所在的长链在 x 子树中的部分。

但是为了让路径之间联通，x 的上面还有两种情形：

  1. 找到 x 上方第一个所在长链排名 \le 2y-1 的点，将其长链的后半截拼到 x 这边。也就是将这条链替换为 x 所在的长链。根据性质 3. 可以知道我们替换其他的长链一定不优
  2. 删去排名为 (2y-1) 的长链，然后向上接上 x 所在长链。该链的贡献是 x 到其上方第一个所在长链排名 \le 2y-2 的点构成的路径。这种情况是在情形 1. 可以找到的长链较优，所以我们在其他无关紧要的地方删去了一条长链。

两种情形都可以使用树上倍增维护，时间复杂度为 \mathcal{O}((n+q)\log n)。

#include<bits/stdc++.h>
#define rd read()
#define gc pa == pb && (pb = (pa = buf) + fread(buf, 1, 100000, stdin), pa == pb) ? EOF : *pa++
using namespace std;
static char buf[100000], * pa(buf), * pb(buf);
inline int read(){
    register int x=0,ss=1,s=gc;
    while(!isdigit(s)&&s!='-')s=gc;if(s=='-')ss=-1,s=gc;
    while(isdigit(s))x=(x<<1)+(x<<3)+(s^48),s=gc;
    return ss*x;
}
const int N=100005;
int n,q,mx,m1,m2,de[N],lg[N];
vector<pair<int,int> > v[N];
struct solver{
    int cnt,mx[N],fa[N],dep[N],son[N],top[N];
    int s[N],sm[N],rk[N],F[19][N];
    pair<int,int> nu[N];
    inline void dfs(int x,int f){
        mx[x]=dep[x],fa[x]=f;
        for(auto [t,w]:v[x])if(t!=f)
            dep[t]=dep[x]+w,dfs(t,x),
            (mx[t]>mx[x])&&(mx[x]=mx[son[x]=t]);
    }
    inline void dfs2(int x,int t){
        top[x]=t,s[t]=max(s[t],dep[x]-dep[fa[t]]);
        if(!son[x])return;dfs2(son[x],t);
        for(auto [u,w]:v[x])
            if(u!=fa[x]&&u!=son[x])dfs2(u,u);
    }
    inline void B(int rt){
        dfs(rt,0),dfs2(rt,rt);
        for(int i=1;i<=n;++i)if(s[i])nu[++cnt]={-s[i],i};
        stable_sort(nu+1,nu+cnt+1);
        for(int i=1;i<=cnt;++i)rk[nu[i].second]=i;
        for(int i=1;i<=n;++i)rk[i]=rk[top[i]],F[0][i]=fa[i],s[i]=s[top[i]];
        for(int i=1;i<=lg[n];++i)
            for(int j=1;j<=n;++j)F[i][j]=F[i-1][F[i-1][j]];
        for(int i=1;i<=cnt;++i)sm[i]=sm[i-1]-nu[i].first;
    }
    inline int Q(int x,int y){
        y=(y<<1)-1;int p=x,P=x;
        if(rk[x]<=y)return sm[min(y,cnt)];
        for(int i=18;~i;--i)
            (rk[F[i][p]]>=y)&&(p=F[i][p]),
            (rk[F[i][P]]>y)&&(P=F[i][P]);
        return mx[x]+max(sm[y-1]-dep[fa[p]],sm[y]-mx[fa[P]]);
    }
}F,G;
inline void dfs(int x,int f){
    if(de[x]>de[m1])m1=x;
    for(auto [t,w]:v[x])
        if(t!=f)de[t]=de[x]+w,dfs(t,x);
}
signed main(){
    for(int i=2;i<N;++i)lg[i]=lg[i>>1]+1;
    n=rd,q=rd;
    for(int i=1,x,y,l;i<n;++i)
        x=rd,y=rd,l=rd,
        v[x].push_back({y,l}),
        v[y].push_back({x,l});
    dfs(1,0),de[m2=m1]=0,dfs(m1,0),
    F.B(m1),G.B(m2);
    for(int i=1,x,y,lt=0;i<=q;++i)
        x=(rd+lt-1)%n+1,y=(rd+lt-1)%n+1,
        cout<<(lt=max(F.Q(x,y),G.Q(x,y)))<<'\n';
    return 0;
}