题目链接Problem - 7524
分析：
我们发现最重要的一个条件是：父节点的ai,bi都会比子节点的ai,bi(对应)大。
那么单独考虑ai,可以发现，按dfs序是可以办到“父——>子”这一过程的。
题目又限制父子节点关系和ai,bi大小关系是充要条件，那么不能把A的儿子ai,bi设的“太小”使其错误地成为了某个B的儿子。
为了儿子“不乱窜”，在同样dfs遍历取bi的时候，对于某节点的儿子应当遍历顺序和ai相反。
dfsa和dfsb很好写，定义一个全局变量now初值为n,每dfs一次now--,这样父节点的值一定比子节点大。
void dfsa(int p){
a[p]=now--;
for(auto x:v[p]){
dfsa(x);
}
}
void dfsb(int p){
b[p]=now--;
for(auto x:v[p]){
dfsb(x);
}
}由于题目要求字典序最小，ai 在bi之前输出，所以我们考虑贪心ai。我们要尽量让标号小的ai后被dfs到，标号大的先被dfs到。
于是，我们开一个va[N]数组，存这个节点及其所有子节点标号最小值。在dfsa时按这个顺序跑。
int dfs(int p){
va[p]=min(p,va[p]);
for(auto x:v[p]){
va[p]=min(va[p],dfs(x));
}
return va[p];
}最后注意跑dfsb之前，子节点遍历顺序反向，now赋值为n。
总代码如下：
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
//祖先的值总比儿子大，则值应当满足dfs序
//为了ai bi不会同序（同序会出现非父子关系出现同大同小）
//又ai先，所以贪心ai,bi遍历儿子时反ai序即可
//为了贪心ai,所以按照节点所有子节点最小标号给其赋值
const int N=200005;
int a[N],b[N];
int va[N];
vector<int>v[N];
int n;
int now=1;
int dfs(int p){
va[p]=min(p,va[p]);
for(auto x:v[p]){
va[p]=min(va[p],dfs(x));
}
return va[p];
}
void dfsa(int p){
a[p]=now--;
for(auto x:v[p]){
dfsa(x);
}
}
void dfsb(int p){
b[p]=now--;
for(auto x:v[p]){
dfsb(x);
}
}
void solve(){
scanf("%d",&n);
for(int i=1;i<=n+1;i++){
v[i].clear();
va[i]=10000000;
}
for(int i=2;i<=n;i++){
int x;
scanf("%d",&x);
v[x].push_back(i);
}
va[1]=dfs(1);
for(int i=1;i<=n;i++){
sort(v[i].begin(),v[i].end(),[](int a,int b)->bool{return va[a]>va[b];});
}
now=n;
dfsa(1);
now=n;
for(int i=1;i<=n;i++){
reverse(v[i].begin(),v[i].end());
}
dfsb(1);
for(int i=1;i<=n;i++){
printf("%d %d",a[i],b[i]);
if(i<n) printf(" ");
}
return ;
}
int main(){
int t;
scanf("%d",&t);
while(t--){
solve();
if(t) printf("\n");
}
return 0;
}