Tập con trọng số lớn nhất

Cho một cây gồm $n$ đỉnh, đánh số từ $1$ đến $n$. Đỉnh thứ $v$ có trọng số $a_v$.

Khoảng cách giữa hai đỉnh trong cây là số cạnh trên đường đi đơn giản nối chúng.

Hãy tìm một tập con các đỉnh có tổng trọng số lớn nhất (trọng số của tập là tổng trọng số các đỉnh trong tập), sao cho không tồn tại cặp đỉnh nào trong tập có khoảng cách nhỏ hơn hoặc bằng $k$.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $k$: số đỉnh của cây và ràng buộc khoảng cách.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$: trọng số các đỉnh.
• $n-1$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u$ và $v$ mô tả một cạnh nối đỉnh $u$ và đỉnh $v$.

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

Dữ liệu ra

In ra một số nguyên: tổng trọng số lớn nhất của tập con mà mọi cặp đỉnh trong tập đều có khoảng cách lớn hơn $k$.

Ràng buộc

• $1\le n,k\le 200$
• $1\le a_i\le {10}^5$
• $1\le u,v\le n$, $u\ne v$

Ví dụ