刚刚比赛 T1 求正解

#include <bits/stdc++.h>
using namespace std;
#define ul unsigned int
const int MAXN = 1e7 + 5;
vector <ul> dep[MAXN],e[MAXN];
ul tot,head[MAXN],_in[MAXN],maxdep;
void dfs(ul u,ul fa,ul depth){
	dep[depth].emplace_back(u);
	if(depth > maxdep) maxdep = depth;
	for(ul v:e[u]){
		if(v != fa) dfs(v,u,depth+1);
	}
}
vector<int> eert(int N,std::vector<int> f){
	vector <int> ans;
	vector <ul> tr[N];
	if(N == 1){
		ans.emplace_back(1);
		return ans;
	}
	int flag1 = 1, flag2 = 1;
	for(ul i=0;i<f.size();++i){
		if(f[i] != 1) flag1 = 0;
		if(f[i] != i+1) flag2 = 0;
	}
	if(flag1) return ans;
	if(flag2){
		if(N<=3&&N!=1) return ans;
		int l = 1, r = N;
		for(int i=1;i<N;++i){
			if(i == 1) ans.push_back((N+1)/2),ans.emplace_back(r), --r;
			else if(i % 2 == 0) ans.emplace_back(l++);
			else ans.emplace_back(r--); 
		}
		return ans;
	}
	for(int i=0;i<f.size();++i){
		e[i+2].emplace_back(f[i]);
		e[f[i]].emplace_back(i+2);
		_in[i+2]++, _in[f[i]]++;
	}
	int n = N, rt = 1;
	for(int i=1;i<=n;++i){
		if(_in[i] == 1){
			rt = i; break;
		}
	}
	dfs(rt,0,1);
	if(maxdep<=3&&maxdep!=1) return ans;
	ul l = 1, r = maxdep;
	for(ul i=1;i<maxdep&&l<r;++i){
		if(i == 1){
			int mid = (maxdep+1) >> 1;
			for(int j:dep[mid]){
				ans.emplace_back(j);
			}
			for(int j:dep[r]){
				ans.emplace_back(j);
			}
			--r;
		}
		else if(i % 2 == 0){
			for(int j:dep[l]) ans.emplace_back(j);
			++l;
		}
		else{
			for(int j:dep[r]) ans.emplace_back(j);
			--r;
		}
	}
	return ans;
}

namespace CHECKER{
	int N;
	vector<int> f;
	vector<int> ans;
	vector<int> vis;
	bool checker(){
		if(ans.size()!=N) return 0;
		for(int i=0;i<N;i++) if(ans[i]<=0||N<ans[i]) return 0;
		vis.resize(N,0);
		for(int i=0;i<N;i++){
			if(vis[ans[i]-1]) return 0;
			vis[ans[i]-1]=1;
		}
		int u,v;
		for(int i=1;i<N;i++){
			u=ans[i-1];
			v=ans[i];
			if(u!=1&&f[u-2]==v||v!=1&&f[v-2]==u) return 0;
		}
		return 1;
	}
	int main(){
		scanf("%d",&N);
		f.resize(N-1);
		for(int i=0;i<N-1;i++){
			scanf("%d",&f[i]);
		}
		ans=eert(N,f);
		if(ans.empty()){
			printf("NO\n");
			return 0;
		}
		if(checker()) printf("YES\n");
		else printf("Wrong answer\n");
		for(int i=0;i<ans.size();i++){
			printf("%d ",ans[i]);
		}
		printf("\n");
		return 0;
	}
}
signed main(){
	return CHECKER::main();
}