题目描述

给定一棵 n 个顶点的带权树和 m 个询问。

对于询问 q_i，求有多少对顶点 (u,v) 满足 u<v，并且 u 到 v 的简单路径上最大边权不超过 q_i。

输入格式

第一行 n,m (1 <= n,m <= 200000)。

接下来 n-1 行，每行 u,v,w (u != v, 1 <= w <= 200000)，表示一条树边。

最后一行包含 m 个询问 q_i (1 <= q_i <= 200000)。

输出格式

按输入顺序输出 m 个询问的答案。

样例 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