G. Path Queries
divide and conquer; dsu; graphs; sortings; trees
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: