trang chủ / bài tập / treedestr

Phá huỷ cây

Đề bài

Mô tả

Cho một cây gồm n đỉnh và n1 cạnh (đồ thị liên thông, từ một đỉnh bất kỳ có thể đi tới mọi đỉnh khác chỉ qua các cạnh của cây).

Ta thực hiện thao tác phá huỷ các đỉnh theo quy tắc sau:

  • Một đỉnh chỉ có thể bị phá huỷ nếu bậc hiện tại của nó là số chẵn (bậc bằng 0 cũng được coi là chẵn).
  • Khi một đỉnh bị phá huỷ, tất cả các cạnh còn nối với nó cũng bị xoá khỏi cây (nên bậc của các đỉnh kề với nó sẽ giảm đi).

Hãy phá huỷ tất cả các đỉnh của cây, hoặc chỉ ra 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 pi0 thì có một cạnh nối giữa đỉnh i và đỉnh pi. Dữ liệu đảm bảo đồ thị cho trước là một cây.

Dữ liệu ra

  • Nếu không thể phá huỷ hết mọi đỉnh, in ra một dòng chứa NO.
  • Ngược lại, in ra dòng đầu tiên là YES. Trong n dòng tiếp theo, in ra chỉ số các đỉnh theo đúng thứ tự phá huỷ chúng.

Nếu có nhiều đáp án hợp lệ, in ra một đáp án bất kỳ.

Ràng buộc

  • 1n2·105
  • 0pin

Ví dụ

Input Output Giải thích
5
0 1 2 1 2
YES
1
2
3
5
4
Đỉnh 1 có bậc 2 (kề với 24) nên phá được trước, xoá hai cạnh (1,2)(1,4). Sau đó đỉnh 2 có bậc 2 (kề với 35) nên phá tiếp. Khi không còn cạnh nào, ba đỉnh 3,5,4 có bậc 0 nên phá theo thứ tự tuỳ ý. Các thứ tự hợp lệ khác cũng được chấp nhận.
4
0 1 2 3
NO Cây là một đường thẳng 1234. Không có cách phá huỷ nào để loại bỏ hết cả bốn đỉnh.
1
0
YES
1
Cây chỉ có một đỉnh với bậc 0 (chẵn) nên phá huỷ được ngay.

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.46 awk 1.3.4 gcc 16.1.0 csc 6.12.0.200 g++ 16.1.0 g++-themis 16.1.0 g++17 16.1.0 g++20 16.1.0 g++23 16.1.0 clang++ 22.1.6 dmd 2.112.0 dart 3.12.1 gforth 0.7.3 gfortran 12.2.0 go 1.26.3 groovyc 5.0.6 javac 25.0.3 node 26.2.0 kotlinc 2.3.21 sbcl 2.2.9 lua 5.4.8 nim 2.2.10 fpc 3.2.2 fpc-themis 3.2.2 perl 5.36.0 php 8.5.6 pike 8.0 pypy3 7.3.23 python3 3.14.5 racket 8.7 ruby 4.0.5 rustc 1.96.0 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 tclsh 8.6 bun 1.3.14 deno 2.8.1 v 0.5.1 zig 0.16.0