Cây Táo

Cho một cây có gốc với $n$ đỉnh, gốc là đỉnh $1$. Mỗi đỉnh lá chứa một số táo $a_i$; các đỉnh không phải lá đều có số táo bằng $0$.

Trọng lượng của một cây con là tổng số táo trong tất cả các lá thuộc cây con đó. Ví dụ, trọng lượng của cây con tương ứng với một lá chính là số táo viết tại lá đó.

Cây được gọi là cân bằng nếu với mỗi đỉnh $v$, tất cả các cây con tương ứng với các con của $v$ đều có trọng lượng bằng nhau.

Cho phép loại bỏ một số quả táo khỏi một số lá (chỉ giảm, không thêm). Hãy tính số quả táo ít nhất cần loại bỏ để cây trở nên cân bằng.

Luôn có thể đạt mục tiêu bằng cách loại bỏ tất cả các quả táo.

Dữ liệu vào

• Dòng đầu chứa số nguyên $n$ — số đỉnh của cây.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$ — số táo tại các đỉnh. Đảm bảo $a_i=0$ với mọi đỉnh không phải lá.
• $n-1$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $x_i,y_i$ ($x_i\ne y_i$) mô tả một cạnh của cây.

Đỉnh $1$ là gốc.

Dữ liệu ra

Một số nguyên duy nhất — số táo ít nhất cần loại bỏ để cây trở nên cân bằng.

Ràng buộc

• $2\le n\le {10}^5$
• $0\le a_i\le {10}^8$
• $1\le x_i,y_i\le n$

Ví dụ