Destruction of a Tree
题意翻译
给你一棵树,如果树上的节点有偶数条边与它相连,则这个节点是可删除的,删除这个节点后所有与之相连的边也将删除。判断一棵树是否可以依次删除所有节点。
输入:
第一行:一个整数n
第二行:n个整数Pi,表示编号为i的点与编号为Pi的点相连,保证是一棵树
输出:
可以删除输出"YES",并输出依次删除的点的编号;
不可以则输出"NO"
题目描述
You are given a tree (a graph with $ n $ vertices and $ n-1 $ edges in which it's possible to reach any vertex from any other vertex using only its edges).
A vertex can be destroyed if this vertex has even degree. If you destroy a vertex, all edges connected to it are also deleted.
Destroy all vertices in the given tree or determine that it is impossible.
输入输出格式
输入格式
The first line contains integer $ n $ ( $ 1<=n<=2·10^{5} $ ) — number of vertices in a tree.
The second line contains $ n $ integers $ p_{1},p_{2},...,p_{n} $ ( $ 0<=p_{i}<=n $ ). If $ p_{i}≠0 $ there is an edge between vertices $ i $ and $ p_{i} $ . It is guaranteed that the given graph is a tree.
输出格式
If it's possible to destroy all vertices, print "YES" (without quotes), otherwise print "NO" (without quotes).
If it's possible to destroy all vertices, in the next $ n $ lines print the indices of the vertices in order you destroy them. If there are multiple correct answers, print any.
输入输出样例
输入样例 #1
5
0 1 2 1 2
输出样例 #1
YES
1
2
3
5
4
输入样例 #2
4
0 1 2 3
输出样例 #2
NO
说明
In the first example at first you have to remove the vertex with index 1 (after that, the edges (1, 2) and (1, 4) are removed), then the vertex with index 2 (and edges (2, 3) and (2, 5) are removed). After that there are no edges in the tree, so you can remove remaining vertices in any order.
![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF963B/9b84e98fe96447b82c6a8ccba7a9e4a5189ce14b.png)