给你一个由 $$$n$$$ 个顶点组成的加权树。回想一下,树是一个没有循环的连通图。顶点 $$$u_i$$$ 和 $$$v_i$$$ 通过权重为 $$$w_i$$$ 的边连接。
您收到了 $$$m$$$ 查询。第 $$$i$$$ 查询以整数 $$$q_i$$$ 形式给出。在此查询中,您需要计算顶点对 $$$(u, v)$$$ ($$$u < v$$$) 的数量,以便 $$$u$$$ 和 $$$v$$$ 之间的简单路径上的边的最大权重不超过 $$$q_i$$$。
输入
输入的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n, m \le 2 \cdot 10^5$$$) — 树中的顶点数和查询数。
接下来的 $$$n - 1$$$ 行描述了树的一条边。边 $$$i$$$ 由三个整数 $$$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$$$),其中 $$$q_i$$$ 是第 $$$i$$$ 查询中边的最大权重。
输出
打印 $$$m$$$ 整数 — 查询的答案。第 $$$i$$$ 值应等于顶点对 $$$(u, v)$$$ ($$$u < v$$$) 的数量,以便 $$$u$$$ 和 $$$v$$$ 之间的简单路径上的边的最大权重不超过 $$$q_i$$$。
查询按输入顺序从 $$$1$$$ 到 $$$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
输出 #1
21 7 15 21 3
输入 #2
1 2 1 2
输出 #2
0 0
输入 #3
3 3 1 2 1 2 3 2 1 3 2
输出 #3
1 3 3
注意
图片显示了第一个示例中的树: