冷门科技 —— DFS 序求解 LA

· · 算法·理论

dfs 序求 k 级祖先无论是在实际效率，空间常数还是好写程度均吊打长链剖分。

定义

  1. dfs 序表示对一棵树进行深度优先搜索得到的结点序列。
  2. 设 d_i 为点 i 的深度，其中根的深度为 1。

算法介绍

考虑现在我们要求节点 u 的第 k 级祖先，设答案为 f，则 d_f 是已知的。

那我们现在在所有深度是 d_f 的点中找到 u 的祖先即可。

显然，f 是 u 的祖先当且仅当以 f 为根的子树包含以 u 为根的子树。

于是可以转为 dfs 序。

设点 x 的后代在 dfs 序上对应的区间为 [l_x,r_x]，那么查询就是问在深度为 d_f 对应的点对应的区间中，是 [l_u,r_u] 的超集的是哪个点，显然只会存在一个，二分秒了。

然后你发现可以将 l_u 或 r_u 丢掉，只保留一个，仍然可以做。

但是保留 r_u 就可以直接用 lower_bound，所以我们选择保留 r_u。

这是 P5903 【模板】树上 K 级祖先的代码。

875 字节，厉不厉害？

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,q,dep[500005],cnt,r[500005];
int nxt[500005],head[500005];
vector<pair<int,int>>vec[500005];
unsigned s;
void add(int u,int v){
    nxt[v]=head[u];
    head[u]=v;
}
inline unsigned get(unsigned x){
    x^=x<<13;
    x^=x>>17;
    x^=x<<5;
    return s=x;
}
void dfs(int u){
    r[u]=++cnt;
    for(int v=head[u];v;v=nxt[v]){
        dep[v]=dep[u]+1;
        dfs(v);
        r[u]=r[v];
    }
    vec[dep[u]].push_back({r[u],u});
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>q>>s;
    int rt=0;
    for(int i=1;i<=n;i++){
        int f(0);
        cin>>f;
        rt+=(!f)*i;
        if(f)add(f,i);
    }
    dep[rt]=1;
    dfs(rt);
    int lst=0,sum=0;
    for(int i=1;i<=q;i++){
        int u=(get(s)^lst)%n+1,k=(get(s)^lst)%dep[u];
        lst=lower_bound(vec[dep[u]-k].begin(),vec[dep[u]-k].end(),make_pair(r[u],-1ll))->second;
        sum^=1ll*i*lst;
    }
    cout<<sum;
    return 0;
}

当然，这份代码显然不是跑得很快的，这份才是：

:::success[]

#include<bits/stdc++.h>
using namespace std;
int n,q,dep[500005],cnt,r[500005];
vector<int>g[500005];
vector<pair<int,int>>vec[500005];
unsigned s;
inline unsigned get(unsigned x){
    x^=x<<13;
    x^=x>>17;
    x^=x<<5;
    return s=x;
}
void dfs(int u){
    r[u]=++cnt;
    for(int v:g[u]){
        dep[v]=dep[u]+1;
        dfs(v);
        r[u]=max(r[u],r[v]);
    }
    vec[dep[u]].push_back({r[u],u});
}
void read(auto&x){
    char c(getchar());
    while(c<'0')c=getchar();
    while(c>='0')x=(x<<1)+(x<<3)+(c^48),c=getchar();
}
signed main(){
    read(n),read(q),read(s);
    int rt=0;
    for(int i=1;i<=n;i++){
        int f(0);
        read(f);
        rt+=(!f)*i;
        g[f].push_back(i);
    }
    dep[rt]=1;
    dfs(rt);
    int lst=0;
    long long sum=0;
    for(int i=1;i<=q;i++){
        int u=(get(s)^lst)%n+1,k=(get(s)^lst)%dep[u];
        lst=lower_bound(vec[dep[u]-k].begin(),vec[dep[u]-k].end(),make_pair(r[u],-1))->second;
        sum^=1ll*i*lst;
    }
    cout<<sum;
    return 0;
}

:::

和各种 LA 算法的对比

对比 DFS 序和重链剖分，预处理的时间常数减半（重链剖分需要两次 dfs），而且更好写，但两种算法表现都不错，因此树剖 LA 也是不错的选择。

对比 DFS 序和倍增，前者预处理复杂度更优，查询常数也更小。

对比 DFS 序和长链剖分，前者预处理复杂度更优，且实际效率也更高（访问连续性）。

对于其它算法，请读者自行比较。