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.

给你一棵树(一个包含 nn 个顶点和 n−1n-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.

第一行包含一个整数 nn(1≤n≤2⋅1051 \leq n \leq 2 \cdot 10^5)——树中顶点的数量。

第二行包含 nn 个整数 p1, p2, …, pnp_1,\,p_2,\,\dots,\,p_n(0≤pi≤n0 \leq p_i \leq n)。若 pi≠0p_i \neq 0,则在顶点 ii 与 pip_i 之间存在一条边。保证所给图是一棵树。

输出格式

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测评打分。不知道怎么写?

首页