Cau mày (cây màu)

View as PDF
Submit solution
Points: 0.01 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout
Author:
bedao
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Cho một cây gồm ~n~ đỉnh có gốc tại đỉnh ~1~. Đỉnh thứ ~i~ (~1 \leq i \leq n~) được gán màu sắc là ~c_i~.

Với mỗi đỉnh ~i~, xác định số màu sắc phân biệt có trong cây con gốc ~i~.

Input

  • Dòng đầu chứa số nguyên dương ~n~ (~1 \leq n \leq 2 \times 10^5~).

  • Dòng thứ hai chứa ~n~ số nguyên dương cách nhau bởi dấu cách biểu diễn mảng ~c~, với ~c_i~ là màu sắc của đỉnh thứ ~i~ (~1 \leq c_i \leq 10^9~).

  • ~n-1~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~a, b~ biểu diễn một cạnh hai chiều giữa đỉnh ~a~ và ~b~ (~1 \leq a,b \leq n~).

Output

Gồm một dòng duy nhất chứa ~n~ số nguyên cách nhau bởi dấu cách, số thứ ~i~ là số màu sắc phân biệt trong tất cả các đỉnh thuộc cây con gốc ~i~.

Scoring

Subtask Điểm Giới hạn
1 40 ~n \leq 5000~
2 60 ~n \leq 2 \times 10^5~

Sample Input 1

5
2 3 2 2 1
1 2
1 3
3 4
3 5

Sample Output 1

3 1 2 1 1

Sample Input 2

4
1 1 3 1000
1 2
2 3
2 4

Sample Output 2

3 3 1 1

Notes

  • Trong test đầu tiên, cây con của đỉnh ~1~ bao gồm tất cả các đỉnh trong cây, mang ~3~ giá trị màu sắc khác nhau. Cây con của đỉnh ~3~ bao gồm ba đỉnh là ~3, 4, 5~ lần lượt mang các màu ~2, 2, 1~, có tất cả ~2~ màu sắc phân biệt là màu ~1~ và ~2~.

  • Trong test thứ hai, cây con của đỉnh ~1~ và đỉnh ~2~ đều có ~3~ màu sắc phân biệt là màu ~1, 3, 1000~.

Comments

Please read the guidelines before commenting.