Alice is currently trapped in a maze, which can be seen as a tree. Each edge in the tree has a weight
representing the length of that edge. The leaves of the tree represent the exits, and when Alice reaches a
leaf, it means she has successfully escaped from the maze.
A leaf is defined as a node with degree 1 that is not the root.
Each maze has a difficulty level, denoted as L. When Alice is at a node x in the tree, she can choose to
jump to a node y in her subtree. Let s be the sum of the edge weights along the path from x to y. The
energy spent when jumping from x to y is (s − L) 2 .
Alice wants to know the minimum amount of energy required to escape the maze if the tree has p as the
root and she starts from p. Alice will ask this question a total of Q times.
The data guarantees that for any given pair of points x and y, the absolute value of the sum of edge
weights s along the path between them does not exceed 109 .
输入格式
The input consists of multiple test cases. The first line contains a single integer T(1 ≤ T ≤ 5) — the
number of test cases. Description of the test cases follows.
The first line of each test case contains two integers n, L (3 ≤ n ≤ 105 , −105 ≤ L ≤ 105 )— the number of
nodes in the tree.
Each of the next n − 1 lines contains three integers u, v, w (1 ≤ u, v ≤ n, u 6= v, −105 ≤ w ≤ 105 ) .
The next line contains a positive integer Q (1 ≤ Q ≤ 10).
Each of the next Q lines contains one integer p (1 ≤ p ≤ n) asks the minimum amount of energy required
to escape the maze if the tree has p as the root and she starts from p.
It is guaranteed that the given graph is a tree.
输出格式
For each test case, output Q lines. Each line should contain a integer indicating the minimum amount of
energy required.
The data guarantees that the answer will not exceed the range that can be represented by a 64-bit signed
integer.