Cây con

Cho một cây gồm $n$ đỉnh đánh số từ $1$ đến $n$, gốc là đỉnh $1$. Đỉnh $v$ mang giá trị $a_v$.

Cây con của đỉnh $v$ gồm chính $v$ và mọi đỉnh mà đường đi từ đỉnh đó về gốc đi qua $v$.

Với mỗi đỉnh $v$, hãy tính số đỉnh trong cây con của $v$ và tổng giá trị các đỉnh trong cây con của $v$.

Lưu ý: mỗi cạnh được cho dưới dạng hai đầu mút theo thứ tự 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 $a_1,a_2,\dots ,a_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 nối $u$ và $v$.

Dữ liệu đảm bảo các cạnh tạo thành một cây.

Dữ liệu ra

• Dòng thứ nhất: $n$ số nguyên, số thứ $v$ là số đỉnh trong cây con của $v$.
• Dòng thứ hai: $n$ số nguyên, số thứ $v$ là tổng giá trị các đỉnh trong cây con của $v$.

Ràng buộc

• $1\le n\le 2·{10}^5$
• $1\le a_v\le {10}^9$
• $1\le u,v\le n$, $u\ne v$

Ví dụ