#1074. COLORGRAPH - MÀU TRÊN CÂY

Bộ nhớ: 256 MiB Thời gian: 1000 ms Nhập/xuất từ luồng chuẩn
Kiểu bài: Thông thường Kiểu chấm: So sánh văn bản
Đưa lên bởi: Trùm CUỐI

Đề bài

NGUỒN: PreVNOI Ⅶ Lần 2 (ONLINE 2017)

Cho một cây gồm N đỉnh, mỗi đỉnh có một màu khác nhau. Gọi d\left(u, v\right) là số màu phân biệt trên đường đi từ đỉnh u tới đỉnh v . Đặt sum(u) = d(u, 1) + d(u, 2) + … + d(u, N) . Hãy tính sum(u) với mọi đỉnh u bất kì.

Dữ liệu vào:

  • Dòng đầu tiên chứa số nguyên N .
  • Dòng thứ hai chứa N số nguyên c_1,c_2,…,c_N lần lượt là màu của các đỉnh.
  • 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 nối giữa hai đỉnh u v . Dữ liệu vào đảm bảo đồ thị có dạng là cây.

Dữ liệu ra:

  • Gồm N dòng, dòng thứ i chứa số nguyên sum(i) .

Ví dụ:

Dữ liệu vào:
5
1 2 3 2 3
1 2
2 3
2 4
1 5
Dữ liệu ra:
10
9
11
9
12
Giải thích:

Giới hạn:

  • 1≤c_i≤10^5 với mọi 1≤i≤N
  • Subtask # 1 : 10\% số điểm: N\le300
  • Subtask # 2 : 18\% số điểm: N\le5000
  • Subtask # 3 : 12\% số điểm: Mọi đỉnh có cùng màu
  • Subtask # 4 : 24\% số điểm: Không tồn tại hai đỉnh cùng màu
  • Subtask # 5 : 36\% số điểm: Không có ràng buộc gì thêm.