405362: GYM101915 G Robots

Memory Limit:256 MB Time Limit:5 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

G. Robotstime limit per test5 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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

Input

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 ≤ 105).

The following n - 1 lines contain 3 integers ui, vi, wi. This means that there is an edge connecting nodes ui and vi, with weight wi. (1 ≤ ui, vi ≤ n) (1 ≤ wi ≤ 109). It's guaranteed that all wi are distinct.

The following line contains q integers xi. (1 ≤ xi ≤ 109).

Output

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

ExampleInput
1
5 7
1 2 3
1 3 4
3 4 9
3 5 7
1 3 4 9 8 7 10
Output
21
Note

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

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

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

加入题单

上一题 下一题 算法标签: