405362: GYM101915 G Robots

The Robotics Olympiad teams were competing in a contest.

There was a tree drawn on the floor, consisting of n nodes and n - 1 edges. The nodes are numbered from 1 to n, and each edge has a weight. The tree is rooted at the first node. q teams are participating, and each team is given an integer x_i. Their robot should start at node 1, and move in the following way until there are no valid moves left: From all the edges between the current node and it's children, go through the edge with the maximum value less than x_i. Note that the robot can't move to the parent, only to children.

However, the teams weren't able to program the robots to return to them after the contest, so they had to manually pick them up. Since the tree can be quite large, they need your help to determine where each robot ended it's movement.

The first line contains a single integer T, the number of test cases.

The first line of each test case contains two space-separated integers n and q. (1 ≤ n, q ≤ 10⁵).

The following n - 1 lines contain 3 integers u_i, v_i, w_i. This means that there is an edge connecting nodes u_i and v_i, with weight w_i. (1 ≤ u_i, v_i ≤ n) (1 ≤ w_i ≤ 10⁹). It's guaranteed that all w_i are distinct.

The following line contains q integers x_i. (1 ≤ x_i ≤ 10⁹).

For each test case, print one line with a single number S_i, the sum of numbers of nodes where each robot ends.

1
5 7
1 2 3
1 3 4
3 4 9
3 5 7
1 3 4 9 8 7 10

21

In the sample test case, the robots end in the following nodes: {1, 1, 2, 5, 5, 3, 4}.

S_i = 1+1+2+5+5+3+4 = 21.

Large I/O files. Please consider using fast input/output methods.