题解：P5353 树上后缀排序

STARSczyy · 2024-08-08 10:38:40 · 题解

一个所有本题题解都没有提及的新思路，并为最优解。只需在后缀排序模板代码上改动极小部分即可，思路简单。

首先看到这道题，第一个想法就是在后缀排序模板基础上改。

好的，这是后缀排序模板伪代码：

#define rep(i,l,r) for(int i=(l),i##end=(r);i<=i##end;++i)
#define per(i,r,l) for(int i=(r),i##end=(l);i>=i##end;--i)
//输入略
rep(l,0,log2(n)){
  rep(i,1,n) a[i]=rk[i],b[i]=i+(1<<l)<=n?rk[i+(1<<l)]:0;//此为为两关键字赋值
  //按两关键字排序略
}

考虑如何修改以上代码。假设我们不考虑从两个节点所对应字符串相同的情况，只求每个节点对应字符串的排名（这里，排名指小于当前字符串的字符串个数加一），那么我们只需改动一行，再加一行：

#define rep(i,l,r) for(int i=(l),i##end=(r);i<=i##end;++i)
#define per(i,r,l) for(int i=(r),i##end=(l);i>=i##end;--i)
//输入部分同上
rep(l,0,log2(n)){
  rep(i,1,n) a[i]=rk[i],b[i]=rk[fa[i]];//此为为两关键字赋值
  //按两关键字排序部分同上
  per(i,n,1) fa[i]=fa[fa[i]];//更新父亲
}

我们发现，此时排名会有相同部分。

我们再来看一下，题目让我们求的是什么。在我们仔细读题后，我们发现，题目让我们求的实际上是 n 个 n+1 元组的排序问题。其中，每个元组第一个元素是这个节点的排名，接下来依次是从根节点到该节点的节点标号，剩下的用 0 来补全。

以样例为例，每个节点所对应的元组为：

空余部分为 0。其中，第一列为 rk 数组，往后依次为根节点到该节点的节点。对以上排序的结果就是答案。

考虑如何求解以上问题。我们可以在求出 rk 数组以后，再从根节点开始 dfs 一遍，每个节点的儿子枚举顺序按从小到大 dfs ，也就是我们用 vector 存树，dfs 时排一遍序。同时，使用桶存 rk，若有重复 rk，加上前面枚举到当前 rk 值的个数。最后用 rk 还原出 sa 数组，整道题就完成啦！！

最终伪代码：

vector<int> e[maxn];
void dfs(int x){
    rk[x]+=t[rk[x]]++,sort(e[x].begin(),e[x].end());
    for(int i:e[x]) dfs(i);
}

#define rep(i,l,r) for(int i=(l),i##end=(r);i<=i##end;++i)
#define per(i,r,l) for(int i=(r),i##end=(l);i>=i##end;--i)
//输入部分同上
rep(i,1,n) e[fa[i]].push_back(i);
rep(l,0,log2(n)){
  rep(i,1,n) a[i]=rk[i],b[i]=rk[fa[i]];//此为为两关键字赋值
  //按两关键字排序部分同上
  per(i,n,1) fa[i]=fa[fa[i]];//更新父亲
}
dfs(1);
rep(i,1,n) sa[rk[i]]=i;

ac 代码如下：

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/rope>
#define rep(i,l,r) for(int i=(l),i##end=(r);i<=i##end;++i)
#define per(i,r,l) for(int i=(r),i##end=(l);i>=i##end;--i)
// #define int long
#define double long double
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define rbtree(way) tree<way,null_type,less<way>,rb_tree_tag,tree_order_statistics_node_update>
using namespace std;
using namespace __gnu_cxx;
using namespace __gnu_pbds;
const int maxn=1e6+10,maxm=1e6+10,mod=998244353,inf=INT_MAX;

int n,a[maxn],b[maxn],t[maxn],rk[maxn],sm[maxn],fa[maxn];
vector<int> e[maxn];
string s;
void dfs(int x){
    rk[x]+=t[rk[x]]++,sort(e[x].begin(),e[x].end());
    for(int i:e[x]) dfs(i);
}

signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n;
    rep(i,2,n) cin>>fa[i],e[fa[i]].pb(i);
    cin>>s;
    rep(i,1,n) ++t[s[i-1]+1];
    rep(i,1,1000) t[i]+=t[i-1];
    rep(i,1,n) rk[i]=t[s[i-1]]+1;
    rep(l,0,log2(n)){
        rep(i,0,n) t[i]=sm[i]=0;
        rep(i,1,n) a[i]=rk[i],b[i]=rk[fa[i]],++t[b[i]+1];
        rep(i,1,n) t[i]+=t[i-1];
        rep(i,1,n) sm[++t[b[i]]]=i;
        rep(i,0,n) t[i]=0;
        rep(i,1,n) rk[sm[i]]+=t[a[sm[i]]]++;
        rep(i,1,n) sm[rk[i]]=i;
        rep(i,1,n) if(a[sm[i-1]]==a[sm[i]]&&b[sm[i-1]]==b[sm[i]]) rk[sm[i]]=rk[sm[i-1]];
        per(i,n,1) fa[i]=fa[fa[i]];
    }
    rep(i,0,n) t[i]=0;
    dfs(1);
    rep(i,1,n) sm[rk[i]]=i;
    rep(i,1,n) cout<<sm[i]<<' ';
    return 0;
}