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\n");

	else{

		printf("YES\n");

		for(auto i:ans)	printf("%d\n", i);

	}

	return 0;

}
巴特西

cf963b Destruction of a Tree

最新文章

热门文章
