Đặt bảo vệ trên cây

Một khu dân cư có $n$ ngôi nhà đánh số từ $1$ đến $n$, nối với nhau bởi $n-1$ con đường sao cho từ một nhà có thể đi tới mọi nhà khác (các nhà và con đường tạo thành một cây). Thuê bảo vệ đứng ở nhà $v$ tốn $c_v$ đồng. Một bảo vệ đứng ở nhà $v$ trông được chính nhà $v$ và mọi nhà nối trực tiếp với $v$ bởi một con đường.

Hãy chọn các nhà để đặt bảo vệ sao cho nhà nào cũng được ít nhất một bảo vệ trông, với tổng chi phí nhỏ nhất.

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 $c_1,c_2,\dots ,c_n$.
• $n-1$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u,v$ cho biết có con đường nối nhà $u$ và nhà $v$.

Dữ liệu ra

In ra một số nguyên là tổng chi phí nhỏ nhất.

Ràng buộc

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

Ví dụ