← 返回题目列表

Codeforces · 1213/G

G. 路径查询

中文机器翻译题面 查看原题

给你一个由 $$$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

注意

图片显示了第一个示例中的树: