trang chủ / đề bài / treedest

Phá huỷ cây

Đề bài

Mô tả

Cho một cây gồm n đỉnh, tức là đồ thị vô hướng liên thông có n đỉnh và n−1 cạnh.

Một đỉnh có thể bị phá huỷ nếu tại thời điểm đó bậc của nó là số chẵn (bậc 0 cũng là số chẵn, nên một đỉnh cô lập luôn phá huỷ được). Khi một đỉnh bị phá huỷ, mọi cạnh còn lại kề với nó cũng bị xoá khỏi đồ thị, do đó bậc của các đỉnh khác có thể thay đổi sau mỗi lần phá huỷ.

Hãy phá huỷ toàn bộ n đỉnh của cây, hoặc xác định rằng điều đó là không thể.

Dữ liệu vào

  • Dòng đầu chứa số nguyên n là số đỉnh của cây.
  • Dòng thứ hai chứa n số nguyên p1,p2,…,pn. Nếu pi≠0 thì có một cạnh nối đỉnh i và đỉnh pi.

Dữ liệu ra

Nếu không thể phá huỷ hết các đỉnh, in ra một dòng duy nhất chứa NO.

Ngược lại, in ra YES trên dòng đầu tiên, sau đó in n dòng, dòng thứ i chứa chỉ số của đỉnh bị phá huỷ ở bước thứ i. Nếu có nhiều đáp án đúng, in ra đáp án bất kỳ.

Ràng buộc

  • 1≤n≤2·105
  • 0≤pi≤n
  • Đúng một giá trị pi bằng 0, và các cạnh tạo thành một cây.

Ví dụ

Input Output Giải thích
5
0 1 2 1 2
YES
1
2
3
5
4
Cây có các cạnh 1−2, 2−3, 1−4, 2−5. Đỉnh 1 có bậc 2 nên phá huỷ được ngay, đồng thời xoá hai cạnh 1−2 và 1−4. Khi đó đỉnh 2 còn bậc 2 (nối tới 3 và 5) nên phá huỷ tiếp. Lúc này đồ thị không còn cạnh nào, ba đỉnh 3, 5, 4 có bậc 0 nên phá huỷ theo thứ tự tuỳ ý.
4
0 1 2 3
NO Cây là đường thẳng 1−2−3−4 với 3 cạnh. Mỗi lần phá huỷ một đỉnh xoá đi một số chẵn cạnh, nên tổng số cạnh bị xoá luôn là số chẵn và không thể bằng 3.
5
0 1 1 1 1
YES
1
2
3
4
5
Đỉnh 1 là tâm của hình sao và có bậc 4 là số chẵn, nên phá huỷ trước. Sau đó bốn đỉnh còn lại đều có bậc 0 và phá huỷ theo thứ tự bất kỳ.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0