Codeforces Educational 2E - Lomsat gelral

View as PDF

Submit solution


Points: 0.60 (partial)
Time limit: 2.0s
Memory limit: 256M
Input: stdin
Output: stdout

Suggester:
Problem source:
Codeforces Educational Round 2
Problem types
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

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

Please read the guidelines before commenting.



  • 0
    dohoc12   commented on Jan. 10, 2022, 7:45 p.m.

    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 ạ