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

Điểm: 0,01 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 256M

Input: stdin

Output: stdout

Tác giả:

Dạng bài

Ngôn ngữ cho phép

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~.

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~).

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~.

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

3 1 2 1 1

3 3 1 1

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~.

Bình luận

Hãy đọc nội quy trước khi bình luận.