Tô màu cây

Cho một cây có $n$ đỉnh. Các đỉnh được đánh số từ $1$ đến $n$ và gốc của cây là đỉnh $1$. Một số đỉnh của cây đã được tô màu đen, một số khác thì chưa được tô màu. Ta sẽ tìm cách tô màu cho tất cả các đỉnh.

Thao tác tô màu sẽ được thực hiện như sau: chọn một đỉnh $u$ và một số nguyên $i\ge 0$, rồi tô tất cả các đỉnh $v$ thành màu đen nếu các điều kiện sau thỏa mãn:

• Đỉnh $v$ nằm trong cây con gốc $u$ (cây con gốc $u$ gồm $u$ và mọi hậu duệ của $u$).
• Khoảng cách giữa hai đỉnh $u$ và $v$ chính xác là $i$. Trong đó khoảng cách giữa hai đỉnh $u$ và $v$ là số cạnh nhỏ nhất để đi từ $u$ đến $v$.

Chi phí để tô màu một đỉnh có khoảng cách $i$ là $c_i$. Tại một thao tác tô màu, nếu chọn đỉnh $u$ mà có nhiều hơn một đỉnh $v$ cùng có khoảng cách với đỉnh $u$ bằng $i$ thì các đỉnh này sẽ được tô màu cùng lúc với chi phí là $c_i$. Như vậy mỗi thao tác (chọn $u$ và $i$) có chi phí đúng bằng $c_i$, không phụ thuộc vào số đỉnh được tô. Được phép tô lại một đỉnh đã có màu đen.

Yêu cầu: Tìm cách tô sao cho tất cả các đỉnh đều được tô thành màu đen với chi phí là nhỏ nhất.

Dữ liệu vào

• Dòng đầu chứa số nguyên $n$ $(1\le n\le {10}^6)$.
• Dòng tiếp theo gồm $n$ số nguyên $c_0,c_1,\dots ,c_{n-1}$ $(0\le c_i\le {10}^9)$, với $c_i$ là chi phí để tô màu ở khoảng cách $i$.
• Dòng tiếp theo gồm $n$ số $a_1,a_2,\dots ,a_n$, trong đó $a_i\in \{0,1\}$. Nếu $a_i=0$ thì đỉnh $i$ chưa được tô màu, $a_i=1$ thì đỉnh $i$ đã được tô màu đen.
• $n-1$ dòng tiếp theo, mỗi dòng gồm hai số nguyên $u,v$ $(1\le u,v\le n)$ thể hiện một cạnh của cây.

Dữ liệu ra

In ra một dòng ghi một số là tổng chi phí nhỏ nhất để tô tất cả các đỉnh thành màu đen.

Ràng buộc

• $1\le n\le {10}^6$.
• $0\le c_i\le {10}^9$.
• $a_i\in \{0,1\}$.
• Các cạnh tạo thành một cây.

Subtasks

• Subtask 1 ($20\%$ số test, ứng với $20\%$ số điểm): $n\le 20$.
• Subtask 2 ($30\%$ số test khác, ứng với $30\%$ số điểm): $n\le 200$.
• Subtask 3 ($30\%$ số test khác, ứng với $30\%$ số điểm): $n\le 2000$.
• Subtask 4 ($20\%$ số test còn lại, ứng với $20\%$ số điểm): không có ràng buộc gì thêm.

Ví dụ