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 < v$ ) such that the maximum weight of an edge on a simple path between $u$ and $v$ doesn't exceed $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.

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

The picture shows the tree from the first example: