Màu sắc thống trị trên cây con

Buổi 77 — Tổng kết Trees
Points
85
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề bài

Cho một cây gồm $N$ đỉnh gốc tại đỉnh $1$. Mỗi đỉnh $i$ được tô một màu $c_i$. Trong cây con gốc $u$, một màu được gọi là thống trị nếu số lần xuất hiện của màu đó trong cây con gốc $u$ là lớn nhất (có thể có nhiều màu cùng đạt số lần xuất hiện lớn nhất).

Với mỗi đỉnh $u$ từ $1$ đến $N$, hãy tính tổng các mã màu thống trị trong cây con gốc $u$.

Dữ liệu vào
  • Dòng đầu tiên chứa số nguyên $N$ ($1 \le N \le 10^5$).
  • Dòng thứ hai chứa $N$ số nguyên $c_1, c_2, \dots, c_N$ ($1 \le c_i \le N$).
  • $N - 1$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u, v$ mô tả một cạnh của cây.
Dữ liệu ra
  • In ra $N$ số nguyên trên một dòng, số thứ $u$ là tổng các màu thống trị của cây con gốc $u$.
Ví dụ
Input Output
4
1 2 3 2
1 2
1 3
2 4
2 2 3 2
Giới hạn
  • $1 \le N \le 10^5$, $1 \le c_i \le N$
Draft saved