rt，题目链接

#include <bits/stdc++.h>
//#define int long long
#define Rg register
#define Ri Rg int
#define Il inline
#define vec vector
#define pb push_back
#define fi first
#define se second
#define IT ::iterator

using namespace std;

typedef double db;
typedef pair<int,int> pii;
const int N=5e5,Inf=1e9;
const db eps=1e-8;

int n,fa[N+5][20],de[N+5];
int g[N+5],sa[N+5],ts[N+5],rk[N+5],tk[N+5];
vec<int>v[N+5];
string s;

Il void dfs(int p){
	for(Ri i=1;i<19;i++)fa[p][i]=fa[fa[p][i-1]][i-1];
	de[p]=de[fa[p][0]]+1;
	for(Ri i:v[p])dfs(i);
	return;
}

Il void SA(){
	int ms=125;
	s=" "+s;
	for(Ri i=1;i<=n;i++){
		rk[i]=s[i];
		g[rk[i]]++;
	}
	for(Ri i=1;i<=ms;i++)g[i]+=g[i-1];
	for(Ri i=n;i;i--)sa[g[rk[i]]--]=i;
	for(Ri k=0;(1<<k)<=n;k++){
		memset(g,0,sizeof(g));
		int sn=0,kn=0;
		for(Ri i=1;i<=n;i++){
			g[rk[i]]++;
			if(!fa[i][k])ts[++sn]=i;
		}
		for(Ri i=1;i<=n;i++)if(fa[sa[i]][k])ts[++sn]=sa[i];
		for(Ri i=1;i<=ms;i++)g[i]+=g[i-1];
		for(Ri i=n;i;i--)sa[g[rk[ts[i]]]--]=ts[i];
		for(Ri i=0;i<=n;i++)tk[i]=rk[i];
		for(Ri i=1;i<=n;i++)rk[sa[i]]=((tk[sa[i]]==tk[sa[i-1]]&&tk[fa[sa[i]][k]]==tk[fa[sa[i-1]][k]])?kn:++kn);
		if(kn==n)return;
		ms=kn;
	}
	memset(g,0,sizeof(g));
	for(Ri i=1;i<=n;i++)g[rk[i]]++;
	for(Ri i=1;i<=ms;i++)g[i]+=g[i-1];
	for(Ri i=1;i<=n;i++)rk[i]=g[rk[i]-1]+1;
	return;
}

Il bool cmp(int x,int y){
	return rk[x]<rk[y];
}

Il bool cmp1(int x,int y){
	return ((fa[x][0]^fa[y][0])?rk[fa[x][0]]<rk[fa[y][0]]:x<y);
}

Il void Sort(int d,int l,int r){
	sort(v[d].begin()+l,v[d].begin()+r,cmp1);
	int tmp=rk[v[d][l]]-1;
	for(Ri i=l;i<r;i++)rk[v[d][i]]=++tmp;
	return;
}

signed main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n;
	for(Ri i=2;i<=n;i++){
		cin>>fa[i][0];
		v[fa[i][0]].pb(i);
	}
	cin>>s;
	dfs(1);
	SA();
	for(Ri i=1;i<=n;i++)v[i].resize(0);
	for(Ri i=1;i<=n;i++)v[de[i]].pb(i);
	for(Ri i=1;!v[i].empty();i++){
		sort(v[i].begin(),v[i].end(),cmp);
		int lst=0;
		v[i].pb(0);
		for(Ri j=1;j<v[i].size();j++){
			if(rk[v[i][j]]==rk[v[i][j-1]])continue;
			if(lst<j-1)Sort(i,lst,j);
			lst=j;
		}
	}
	for(Ri i=1;i<=n;i++)sa[rk[i]]=i;
	for(Ri i=1;i<=n;i++)cout<<sa[i]<<' ';
	return 0;
}

谢谢。