Truy vấn cặp đỉnh trên cây

Cho một cây có trọng số gồm $n$ đỉnh (cây là đồ thị liên thông không có chu trình). Cạnh thứ $i$ nối hai đỉnh $u_i$ và $v_i$ và có trọng số $w_i$.

Bạn nhận được $m$ truy vấn. Truy vấn thứ $i$ cho một số nguyên $q_i$. Với truy vấn này, hãy đếm số cặp đỉnh $(u,v)$ với $u<v$ sao cho trọng số lớn nhất của một cạnh trên đường đi đơn giữa $u$ và $v$ không vượt quá $q_i$.

Các truy vấn độc lập với nhau.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $m$ — số đỉnh của cây và số truy vấn.
• $n-1$ dòng tiếp theo, dòng thứ $i$ chứa ba số nguyên $u_i$, $v_i$, $w_i$ mô tả một cạnh nối $u_i$ và $v_i$ với trọng số $w_i$.
• Dòng cuối chứa $m$ số nguyên $q_1,q_2,\dots ,q_m$.

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

Dữ liệu ra

In ra $m$ số nguyên — đáp án cho các truy vấn, theo đúng thứ tự nhập vào. Số thứ $i$ là số cặp đỉnh $(u,v)$ với $u<v$ mà trọng số cạnh lớn nhất trên đường đi giữa chúng không vượt quá $q_i$.

Ràng buộc

• $1\le n,m\le 2·{10}^5$
• $1\le u_i,v_i\le n$, $u_i\ne v_i$
• $1\le w_i\le 2·{10}^5$
• $1\le q_i\le 2·{10}^5$

Ví dụ