Codeforces Educational 2E - Lomsat gelral
View as PDF
Cho một cây không trọng số, có gốc là đỉnh ~1~. Mỗi đỉnh sẽ được tô bằng một màu.
Gọi màu ~c~ là phổ biến trong cây con gốc ~v~ nếu như không tồn tại màu nào khác xuất hiện trong cây con gốc ~v~ nhiều lần hơn hơn màu ~c~. Do đó có thể có nhiều hơn hai màu phổ biến trong một cây con nào đó.
Cây con gốc ~v~ bao gồm đỉnh ~v~ và các đỉnh chứa đỉnh ~v~ trên đoạn đường tới gốc.
Với mỗi đỉnh ~v~, hãy tìm tổng các màu phổ biến xong cây con gốc ~v~.
Input
Dòng thứ nhất chứa một số nguyên ~n~ ~(1 \le n \le 10^5)~ - là số đỉnh trong cây.
Dòng thứ hai gồm ~n~ số nguyên ~c_1, c_2, \ldots, c_n~ ~(1 \le c_i \le n)~ với ~c_i~ là màu của đỉnh thứ ~i~.
~n - 1~ dòng tiếp theo, mỗi dòng gồm hai số nguyên ~x_j, y_j~ ~(1 \le x_j, y_j \le n)~ - là một cạnh của cây.
Output
In ra ~n~ số nguyên trên một dòng với số thứ ~i~ là tổng các màu phổ biến trong cây con gốc ~i~.
Sample 1
Input
4
1 2 3 4
1 2
2 3
2 4
Output
10 9 3 4
Sample 2
Input
15
1 2 3 1 2 3 3 1 1 3 2 2 1 2 3
1 2
1 3
1 4
1 14
1 15
2 5
2 6
2 7
3 8
3 9
3 10
4 11
4 12
4 13
Output
6 5 4 3 2 3 3 1 1 3 2 2 1 2 3
Comments
Câu cuối trong đề hình như phải là trong cây con gốc v chứ ko phải là xong cây con gốc v ạ