CF963B.Destruction of a Tree
普及+/提高
通过率:0%
时间限制:1.00s
内存限制:256MB
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
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.
给你一棵树(一个包含 n 个顶点和 n−1 条边的图,且图中任意两个顶点之间均可仅通过其边相互到达)。
若一个顶点的度数为偶数,则该顶点可以被销毁。当你销毁一个顶点时,所有与之相连的边也会一并被删除。
请销毁给定树中的所有顶点,或判断这是不可能的。
输入格式
The first line contains integer n (1 ≤ n ≤ 2·105) — 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.
第一行包含一个整数 n(1≤n≤2⋅105)——树中顶点的数量。
第二行包含 n 个整数 p1,p2,…,pn(0≤pi≤n)。若 pi=0,则在顶点 i 与 pi 之间存在一条边。保证所给图是一棵树。
输出格式
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.
如果可以摧毁所有顶点,则输出 "YES"(不带引号),否则输出 "NO"(不带引号)。
如果可以摧毁所有顶点,则在接下来的 n 行中,按摧毁顺序输出各顶点的编号。若存在多个正确答案,输出任意一个即可。
输入输出样例
输入#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.

在第一个示例中,首先需要删除索引为 1 的顶点(此后,边 (1, 2) 和 (1, 4) 被移除),然后删除索引为 2 的顶点(边 (2, 3) 和 (2, 5) 被移除)。此后树中不再含有任何边,因此剩余的顶点可以按任意顺序删除。

输入解题思路,AI测评打分。不知道怎么写?