Codeforces Educational 2E - Lomsat gelral

Xem dạng PDF

Gửi bài giải


Điểm: 0,60 (OI)
Giới hạn thời gian: 2.0s
Giới hạn bộ nhớ: 256M
Input: stdin
Output: stdout

Người đăng:
Nguồn bài:
Codeforces Educational Round 2
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 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

Bình luận

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



  • 4
    dohoc12  đã bình luận lúc 10, Tháng 1, 2022, 12:45

    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 ạ