Tập độc lập trọng số lớn nhất trên cây

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

Hãy chọn ra một tập các đỉnh sao cho không có hai đỉnh được chọn nào nối trực tiếp với nhau bởi một cạnh, và tổng giá trị các đỉnh được chọn là lớn nhất. Được phép chọn tập rỗng.

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$ cho biết có cạnh nối đỉnh $u$ và đỉnh $v$.

Dữ liệu ra

In ra một số nguyên là tổng giá trị lớn nhất có thể đạt được.

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ụ