CF1213G · Path Queries

• 难度：1800
• 标签：divide and conquer、dsu、graphs、sortings、trees
• 链接：https://codeforces.com/problemset/problem/1213/G
• 时间限制：3 seconds　内存限制：256 megabytes
• 出现位置：Day12-Kruskal-离线排序-路径贡献

英文原题面

Statement

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$.

Input

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.

Output

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.

样例

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

样例解释（英文原文）

The picture shows the tree from the first example: