Trong hành trình khai phá một hành tinh lạ được nghi ngờ là có sự sống, nhóm thám hiểm của Tèo phát hiện một nền văn minh của một loài sinh vật mà nhóm gọi là loài X, tổ chức sinh sống như một vương quốc. Vương quốc của loài X bao gồm ~n~ thành trì, kết nối với nhau bởi ~n - 1~ con đường hai chiều với thành trì số ~1~ là thành trì của quốc vương loài X . Sau khi tiến hành nghiên cứu sinh học nhân đạo, nhóm của Tèo biết rằng loài X có thể nhận biết tối đa ~n~ màu sắc, và mỗi thành trì trong vương quốc đều được tô một màu bất kì mà chúng có thể nhận biết.
Một khu vực trực thuộc ~v~ bao gồm thành trì ~v~ và các thành trì khác chứa thành trì ~v~ trên đường đi tới thành trì của quốc vương. Gọi màu ~c~ là màu phổ biến của khu vực trực thuộc ~v~ nếu không tồn tại màu nào khác xuất hiện trong khu vực trực thuộc ~v~ nhiều hơn màu ~c~, và tất nhiên một khu vực trực thuộc có thể có nhiều màu phổ biến.
Với mỗi ~v~, nhóm của Tèo muốn biết tổng các màu phổ biến của khu vực trực thuộc ~v~.
Dữ liệu
- Dòng đầu tiên chứa số nguyên ~n~ ~(1 \le n \le 10^5)~.
- ~n - 1~ dòng tiếp theo, mỗi dòng chứa ~2~ số nguyên ~u, v~ mô tả có một đường nối giữa ~2~ thành trì ~u~ và ~v~.
- Dòng cuối cùng chứa ~n~ số nguyên ~c_i~ mô tả màu của thành trì thứ ~i~ ~(1 \le c_i \le n)~.
Kết quả
- Xuất ra một dòng gồm ~n~ số, số thứ ~i~ tổng màu phổ biến của khu vực trực thuộc ~i~.
Giới hạn
- Có ~50\%~ số test có ~n \le 500~
- ~50\%~ số test còn lại không có ràng buộc gì thêm.
Ví dụ
Dữ liệu
4
1 2
2 3
2 4
1 2 2 1
Kết quả
3 2 2 1
Comments