Trong một giờ học tại VP, cô Hương ra một đề bài như sau: Cho một cây N đỉnh, đánh số từ 1 đến N , gốc tại 1, đỉnh i được tô màu a_i. Yêu cầu đếm số lượng màu khác nhau trong cây con gốc i với mọi i từ 1 đến N.

Ví dụ cho cây 6 đỉnh như sau:

Với màu của các đỉnh lần lượt là: 1, 2, 3, 4, 5, 6.

Xét cây con gốc 4, chứa 4 đỉnh: 4, 2, 3, 5. Vì thế nên cây con gốc 4 chứa 4 màu khác nhau.

Tuy nhiên, bài toán này quá khó với Huy. Các bạn hãy giúp Huy giải bài toán này nhé.

• Dòng đầu tiên chứa một số nguyên dương duy nhất N (N \leq 200000).
• N −1 dòng tiếp theo, mỗi dòng chứa hai số nguyên chỉ một cạnh của cây.
• Dòng cuối cùng chứa N số nguyên dương a_i (a_i \leq 200000).

In ra N số nguyên trên một dòng là kết quả bài toán, số thứ i là kết quả của cây con gốc i.

• Subtask 1 (40% số test): 1 \leq N \leq 10^3.
• Subtask 2 (60% số test): Không có ràng buộc gì thêm.