题目描述

给定一棵有 $n$ 个结点的带权树，以及 $m$ 个询问。

对于一个询问值 $q$，求满足 $u<v$ 的结点对 $(u,v)$ 的数量，使得从 $u$ 到 $v$ 的简单路径上最大边权不超过 $q$。

输入格式

第一行输入两个整数 $n,m$（$1 \le n,m \le 2 \cdot 10^5$），分别表示结点数和询问数。

接下来 $n-1$ 行，每行输入三个整数 $u_i,v_i,w_i$（$1 \le u_i,v_i \le n$，$u_i \ne v_i$，$1 \le w_i \le 2 \cdot 10^5$），表示树中的一条边及其边权。

最后一行输入 $m$ 个整数 $q_1,q_2,\dots,q_m$（$1 \le q_i \le 2 \cdot 10^5$），表示各询问值。

保证给出的边构成一棵树。

输出格式

按输入顺序输出 $m$ 个整数，其中第 $i$ 个整数为询问 $q_i$ 的答案。

样例

样例 1

输入：

7 5
1 2 1
3 2 3
2 4 1
4 5 2
5 7 4
3 6 2
5 2 3 4 1

输出：

21 7 15 21 3

样例 2

输入：

1 2
1 2

输出：

0 0

样例 3

输入：

3 3
1 2 1
2 3 2
1 3 2

输出：

1 3 3