Cây thông
Đề bài
Mô tả
Cho một cây có gốc gồm đỉnh, đỉnh là gốc. Mọi cạnh đều hướng từ gốc đi ra: nếu có cạnh hướng từ tới thì là cha của , còn là con của .
Một đỉnh được gọi là 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 đỉ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 là số đỉnh của cây.
- dòng tiếp theo, dòng thứ chứa số nguyên là chỉ số của đỉnh cha của đỉnh .
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
- với mọi
- Đảm bảo gốc (đỉnh ) có ít nhất đỉnh con.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 4 1 1 1 |
Yes | Gốc có ba con , cả ba đều là lá. Đỉnh không phải lá duy nhất là gốc và nó có đúng con là lá. |
| 7 1 1 1 2 2 2 |
No | Gốc có ba con , nhưng đỉnh lại có con (các đỉnh ) nên không phải lá. Vậy gốc chỉ có con là lá ( và ), ít hơn . |
| 8 1 1 1 1 3 3 3 |
Yes | Gốc có bốn con , trong đó không phải lá nên gốc có đúng con là lá. Đỉnh có ba con đều là lá. |
Bình luận