考虑用后缀平衡树来维护这个东西。

后缀平衡树是一种维护后缀的数据结构，其中序遍历就是后缀数组。但是，对于它维护的后缀集合 $T$ 其中的一个字符串 $S\in T$ ，它可以支持 $O(\log n)$ 插入 $xS$ 。

我们考虑插入 $xS$ 的时候要做什么，首先会比较当前节点所代表的后缀的第一个字符和 $x$ 的大小关系，如果不相同，我们就已经成功比较了当前节点的后缀和这个串的大小关系。否则，我们需要比较 $S$ 与这个后缀去掉第一个字符（仍然是个后缀）的大小关系，也就是某两个后缀的大小关系。如果我们对后缀平衡树上每个点分配一个权值，可以 $O(1)$ 进行比较。分配权值可以给整个树分配一个 $[0,10^9]$ 的权值，然后每次折半分配权值。使用替罪羊树来进行重构就可以让树高保持不高。

树上后缀排序同样可以用这个，每次插入的时候可以方便地找到去掉第一个字符的后缀 $fa[u]$ 。

#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "queue"                   
using namespace std;
#define MAXN 600006
//#define int long long
#define rep(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define per(i, a, b) for (int i = (a), i##end = (b); i >= i##end; --i)
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define all(x) (x).begin() , (x).end()
#define mem( a ) memset( a , 0 , sizeof a )
typedef long long ll;
int n , m;
int A[MAXN] , fa[MAXN];
char S[MAXN];

#define alp 0.75
int siz[MAXN] , ch[MAXN][2] , rt;
double val[MAXN];

void pu( int x ) {
	siz[x] = siz[ch[x][0]] + 1 + siz[ch[x][1]];
}

int tr[MAXN] , cn;
void pia( int x ) {
	if( !x ) return;
	pia( ch[x][0] );
	tr[++ cn] = x;
	pia( ch[x][1] );
	ch[x][0] = ch[x][1] = 0;
}
void rebuild( int& x , int l , int r , double L , double R ) {
	if( l > r ) return;
	int m = l + r >> 1; double mid = ( L + R ) / 2;
	x = tr[m] , val[x] = mid;
	rebuild( ch[x][0] , l , m - 1 , L , mid ) , rebuild( ch[x][1] , m + 1 , r , mid , R );
	pu( x );
}
bool fuck( int x ) {
	return siz[x] * alp < siz[ch[x][0]] || siz[x] * alp < siz[ch[x][1]];
}
void maintain( int& x , double L , double R ) {
	if( fuck( x ) ) cn = 0 , pia( x ) , rebuild( x , 1 , cn , L , R );
}
bool cmp( int x , int y ) {
	return S[x] == S[y] ? ( val[fa[x]] == val[fa[y]] ? x < y : val[fa[x]] < val[fa[y]] ) : S[x] < S[y];
}
void ins( int& x , int idx , double L , double R ) {
	if( !x ) {
		x = idx , siz[x] = 1 , val[x] = ( L + R ) / 2;
		return;
	}
	if( cmp( idx , x ) ) ins( ch[x][0] , idx , L , val[x] );
	else ins( ch[x][1] , idx , val[x] , R );
	pu( x );
	maintain( x , L , R );
}
int sa[MAXN] , cnt;
void calc( int x ) {
	if( !x ) return;
	calc( ch[x][0] );
	sa[++ cnt] = x;
	calc( ch[x][1] );
}

void solve() {
	cin >> n;
	rep( i , 2 , n ) scanf("%d",fa + i);
	scanf("%s",S + 1);
	rep( i , 1 , n ) 
		ins( rt , i , 0 , 1e9 );
	calc( rt );
	rep( i , 1 , n ) printf("%d ",sa[i]);
}

signed main() {
//    int T;cin >> T;while( T-- ) solve();
    solve();
}