Bedao OI Contest 3 - Trie hoàn hảo
Xem dạng PDF
Ta định nghĩa một cây Trie như sau:
Cây có gốc.
Mỗi đỉnh ~i~ của cây thể hiện một xâu kí tự, ký hiệu là ~S_i~.
Mỗi cạnh của Trie được gán một kí tự ~c~.
Xâu ký tự ứng với đỉnh gốc là xâu rỗng.
Với mỗi cạnh ~u, v~ được gán ký tự ~c~, trong đó u là đỉnh gần gốc hơn (u là cha của v), ~S_v = S_u + c~.
Cây Trie được gọi là hoàn hảo nếu như tất cả các giá trị ~S_i~ đôi một phân biệt.
Cho một cây ~T~ có ~n~ đỉnh, các cạnh được gán sẵn kí tự. Hãy đếm số đỉnh ~u~ sao cho ~T~ là một cây Trie hoàn hảo nếu chọn ~u~ làm gốc của ~T~.
Input
Vào từ file văn bản trie.inp:
Dòng đầu gồm một số nguyên dương ~n~ là số đỉnh trong cây ~(1 \le n \le 10^5)~.
~n - 1~ dòng tiếp theo, mỗi dòng có dạng ~u~ ~v~ ~c~ thể hiện một cạnh nối từ đỉnh ~u~ đến đỉnh ~v~ và được gán ký tự ~c~ ~(1\le u, v \le n, u \ne v, c~ là chữ cái tiếng Anh viết thường~)~.
Output
In ra file văn bản trie.out một số nguyên duy nhất là số đỉnh có thể chọn làm gốc để thu được
một cây Trie hoàn hảo.
Scoring
| Subtask | Điểm | Giới hạn |
|---|---|---|
| 1 | ~10\%~ | Cây là một đường thẳng (cây gồm ~n-2~ đỉnh có bậc 2 và 2 đỉnh bậc 1) |
| 2 | ~30\%~ | ~n \le 1000~ |
| 3 | ~30\%~ | Các cạnh chỉ được gán một trong 2 ký tự ~'a'~ hoặc ~'b'~ |
| 4 | ~30\%~ | Không có điều kiện gì thêm |
Sample Input 1
10
7 5 w
6 7 w
8 7 b
1 8 v
3 7 f
2 8 a
4 6 y
9 3 m
10 5 q
Sample Output 1
4
Notes
Các đỉnh thỏa mãn là các đỉnh ~5, 6, 4, 10~.
Bình luận
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.