cf963b Destruction of a Tree

越靠近叶子越优先删掉

#include <iostream>
#include <vector>
#include <cstdio>
using namespace std;
int n, uu, hea[200005], cnt, deg[200005], fa[200005];
bool vis[200005];
vector<int> shu;
vector<int> ans;
struct Edge{
	int too, nxt;
}edge[400005];
void add_edge(int fro, int too){
	edge[++cnt].nxt = hea[fro];
	edge[cnt].too = too;
	hea[fro] = cnt;
}
void dfs(int x, int f){
	shu.push_back(x);
	fa[x] = f;
	for(int i=hea[x]; i; i=edge[i].nxt){
		int t=edge[i].too;
		if(t!=f)	dfs(t, x);
	}
}
void shanchu(int x){
	vis[x] = true;
	ans.push_back(x);
	for(int i=hea[x]; i; i=edge[i].nxt){
		int t=edge[i].too;
		deg[t]--;
		if(t!=fa[x] && !vis[t]){
			if(deg[t]%2==0)
				shanchu(t);
		}
	}
}
int main(){
	cin>>n;
	for(int i=1; i<=n; i++){
		scanf("%d", &uu);
		if(!uu)	continue;
		add_edge(uu, i);
		add_edge(i, uu);
		deg[i]++; deg[uu]++;
	}
	dfs(1, 0);
	for(int i=shu.size()-1; i>=0; i--){
		int x=shu[i];
		if(/*vis[x] ||*/deg[x]&1)	continue;
		shanchu(x);
	}
	if(ans.size()!=n)	printf("NO
");
	else{
		printf("YES
");
		for(auto i:ans)	printf("%d
", i);
	}
	return 0;
}