orz negiizhao
自底向上确定每个点的所有出边上挂的字符，那么问题就是比较 \(x,y\) 两个子树的字典序大小。直接一起往下 dfs，先找到标记点的子树更小，如果 dfs 过程中一棵树找完了而另一棵树没找完并且还没确定大小，这时还没找完的那棵树应当排到前面。在递归的最浅层也就是比较 \(x,y\) 时最后特判下标号大小即可。
这里排序使用归并排序 stable_sort，现在来分析一下复杂度：
单独考虑每一层：在归并两个队头分别为 \(u,v\) 的子树序列 \(p,q\) 时，花费 \(\min(size_u,size_v)\) 的时间代价，将其中之一 pop 掉。先把代价放缩成 pop 掉的那个子树的 \(size\)，但如果 pop 掉的是重儿子是把代价记成没有被 pop 掉的那个轻儿子上。这样每个轻儿子计算代价时最多被计算两次，所以同一层所花费的是轻儿子子树和级别的。再算上归并排序一共有 \(\log\) 层，那么时间复杂度就是 \(\mathcal{O}(n\log^2 n)\)．
const int N=200010;
int n,m;
int fa[N],vis[N],col[N],siz[N];
vi eg[N];
void dfs1(int x){
siz[x]=1;
for(auto v:eg[x])dfs1(v),siz[x]+=siz[v];
stable_sort(eg[x].begin(),eg[x].end(),[&](const int &x,const int &y){
function<int(int,int)>cmp=[&](int u,int v){//u<v:1 v<u:-1 u=v:0
if(vis[u]+vis[v]==1)return vis[u]?1:-1;
int len=min(eg[u].size(),eg[v].size());
for(int i=0;i<len;i++){
int t=cmp(eg[u][i],eg[v][i]);
if(t)return t;
}
if(siz[u]==siz[v]){
if(u==x&&v==y)return u<v?1:-1;
return 0;
}
else return siz[u]>siz[v]?1:-1;
};
return cmp(x,y)==1?1:0;
});
int len=eg[x].size();
for(int i=0;i<len;i++)col[eg[x][i]]=i;
}
void solve(){
read(n,m);
for(int i=0;i<=n;i++)vi().swap(eg[i]),vis[i]=0;
for(int i=1;i<=n;i++)read(fa[i]),eg[fa[i]].pb(i);
for(int i=1,x;i<=m;i++)vis[read(x)]=1;
dfs1(0);
for(int i=1;i<=n;i++)putchar('a'+col[i]);
puts("");
}