Cây thông

Đề bài

Mô tả

Cho một cây có gốc gồm n đỉnh, đỉnh 1 là gốc. Mọi cạnh đều hướng từ gốc đi ra: nếu có cạnh hướng từ v tới u thì v là cha của u, còn u là con của v.

Một đỉnh được gọi là nếu nó không có con nào và có cha (tức là mọi đỉnh không có con, ngoại trừ gốc, đều là lá).

Cây được gọi là cây thông nếu mọi đỉnh không phải lá đều có ít nhất 3 đỉnh con là lá. Lưu ý: điều kiện đếm số con là lá, chứ không phải tổng số con, nên một đỉnh có rất nhiều con vẫn có thể vi phạm nếu phần lớn các con đó không phải lá. Gốc luôn được tính là đỉnh không phải lá và cũng phải thỏa điều kiện này.

Hãy kiểm tra xem cây đã cho có phải là cây thông hay không.

Dữ liệu vào

  • Dòng đầu chứa số nguyên n là số đỉnh của cây.
  • n1 dòng tiếp theo, dòng thứ i chứa số nguyên pi là chỉ số của đỉnh cha của đỉnh i+1.

Dữ liệu ra

In ra Yes nếu cây là cây thông, ngược lại in ra No.

Ràng buộc

  • 3n1000
  • 1pii với mọi 1in1
  • Đảm bảo gốc (đỉnh 1) có ít nhất 2 đỉnh con.

Ví dụ

Input Output Giải thích
4
1
1
1
Yes Gốc 1 có ba con 2,3,4, cả ba đều là lá. Đỉnh không phải lá duy nhất là gốc và nó có đúng 3 con là lá.
7
1
1
1
2
2
2
No Gốc 1 có ba con 2,3,4, nhưng đỉnh 2 lại có con (các đỉnh 5,6,7) nên 2 không phải lá. Vậy gốc chỉ có 2 con là lá (34), ít hơn 3.
8
1
1
1
1
3
3
3
Yes Gốc có bốn con 2,3,4,5, trong đó 3 không phải lá nên gốc có đúng 3 con là lá. Đỉnh 3 có ba con 6,7,8 đều là lá.

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.400 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.2 gforth 0.7.3 gfortran 12.2.0 go 1.27.0 groovyc 5.1.1 javac 25.0.4 node 26.8.1 julia 1.12.7 kotlinc 2.4.10 lean 4.33.1 sbcl 2.2.9 lua 5.4.9 nim 2.2.10 fpc 3.2.2 fpc-themis 3.2.2 perl 5.36.0 php 8.5.10 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.14.7 racket 8.7 ruby 4.0.6 rustc 1.98.0 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.3.3 tclsh 8.6 bun 1.4.0 deno 2.9.6 v 0.5.2 zig 0.16.0