阿尔发

#include<bits/stdc++.h>
using namespace std;
vector<int> to[200005];
int n,a,vis[200005],q[200005];
int cmp(int b,int c) {return b>c;}
void ad(int u,int v) {to[u].push_back(v);}
void dfs(int k) 
{
    cout << k << ' ';
    for (int i=0;i<to[k].size();i++) 
	{
        if (vis[to[k][i]]==0) 
		{
            vis[to[k][i]]=1;
            dfs(to[k][i]);
        }
    }
}
void bfs(int k) 
{
    int head=1,tail=1;
    q[tail++]=k;while(head<tail) 
	{
        int now=q[head++];
        cout << now << " ";for (int i=0;i<to[now].size();i++) 
		{
            if (vis[to[now][i]]==0) 
			{
                vis[to[now][i]]=1;
                q[tail++]=to[now][i];
            }
        }
    }
}
int main() 
{
    cin >> n;
    for (int i=1;i<=n-1;i++) 
	{
        cin >> a;
        ad(a,i);
        ad(i,a);
    }
    for (int i=0;i<n;i++) sort(to[i].begin(),to[i].end(),cmp);
    vis[0]=1;
    dfs(0);
    memset(vis,0,sizeof(vis));
    cout << endl;
    vis[0]=1;
    bfs(0);
    return 0;
}