CF1213G.Path Queries

You are given a weighted tree consisting of $n$ vertices. Recall that a tree is a connected graph without cycles. Vertices $u_i$ and $v_i$ are connected by an edge with weight $w_i$.

You are given $m$ queries. The $i$-th query is given as an integer $q_i$. In this query you need to calculate the number of pairs of vertices $(u, v)$ ($u \lt v$) such that the maximum weight of an edge on a simple path between $u$ and $v$ doesn't exceed $q_i$.

你被给定一棵包含 $n$ 个顶点的带权树。请回忆：树是一种无环的连通图。顶点 $u_i$ 和 $v_i$ 之间通过一条权重为 $w_i$ 的边相连。

你将收到 $m$ 个查询。第 $i$ 个查询以整数 $q_i$ 给出。对于该查询，你需要计算满足以下条件的顶点对 $(u, v)$（其中 $u \lt v$）的数量：在 $u$ 与 $v$ 之间的简单路径上，所有边的最大权重不超过 $q_i$。

The first line of the input contains two integers $n$ and $m$ ($1 \le n, m \le 2 \cdot 10^5$) — the number of vertices in the tree and the number of queries.

Each of the next $n - 1$ lines describes an edge of the tree. Edge $i$ is denoted by three integers $u_i$, $v_i$ and $w_i$ — the labels of vertices it connects ($1 \le u_i, v_i \le n$, $u_i \ne v_i$) and the weight of the edge ($1 \le w_i \le 2 \cdot 10^5$). It is guaranteed that the given edges form a tree.

The last line of the input contains $m$ integers $q_1, q_2, \dots, q_m$ ($1 \le q_i \le 2 \cdot 10^5$), where $q_i$ is the maximum weight of an edge in the $i$-th query.

输入的第一行包含两个整数 $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$ 次查询中允许的边的最大权重。

Print $m$ integers — the answers to the queries. The $i$-th value should be equal to the number of pairs of vertices $(u, v)$ ($u \lt v$) such that the maximum weight of an edge on a simple path between $u$ and $v$ doesn't exceed $q_i$.

Queries are numbered from $1$ to $m$ in the order of the input.

输出 $m$ 个整数——即各查询的答案。其中第 $i$ 个值应等于满足以下条件的顶点对 $(u, v)$（其中 $u \lt v$）的数目：在 $u$ 与 $v$ 之间的任意一条简单路径上，所有边的最大权重不超过 $q_i$。

查询按输入顺序编号为 $1$ 至 $m$。

The picture shows the tree from the first example:

图片展示了第一个示例中的树：