Problem Description

Yan loves computer science very much, especially graph theory. So every day at school, he draws a tree and tries hard not to lift his pen from the paper.

Each day, he comes up with a tree with $N$ vertices and starts drawing it from the root. Each edge connecting vertices $a_i$ and $b_i$ has length $l_i$. Starting from the root, he moves along edges without lifting his pen, and he wants to pass through every vertex and every edge at least once. Since drawing alone has become very boring for Yan, he decided to invite friends to help. The rule is as follows: whenever he finishes drawing at some vertex of the tree, he may call a friend to continue drawing — the friend must start from the current vertex and keep drawing under the same “no lifting the pen” constraint.

Yan’s best friend Atina always watches his game with sharp eyes. She scores each drawing by the formula $L + k \times P$, where $L$ is the total length of the path drawn on paper by Yan and his friends (in centimeters), $k$ is the total number of friends Yan called, and $P$ is the “call-a-friend” cost — a value Yan chooses before he starts drawing. Note that if an edge is traversed multiple times, its length is counted multiple times in $L$ (see Sample 1).

To make Atina as happy as possible, Yan wants to choose a price $P$ so that her score is as small as possible. But due to heavy homework, he asks you for help. For each day, he considers different “call-a-friend” cost values $P_i$ and wants to know, under the best drawing strategy, what the minimum possible score from Atina is.

Input Format

The first line of standard input contains an integer $T$ — the number of trees Yan plans to draw. Then, for each tree, its description is given, followed by the different “call-a-friend” cost values you need to answer:

• For each tree: the first line contains $N$ — the number of vertices in the tree.
• The next $N - 1$ lines each contain three integers $a_i, b_i, l_i$, describing an edge between two vertices and its length.
• Then an integer $Q$ is given — the number of different “call-a-friend” costs you need to process.
• The last $Q$ lines each contain one integer $P_i$, the value of the $i$-th cost.

Output Format

For each drawing (i.e., for each tree), output $Q$ numbers — the minimum score Atina can give when the “call-a-friend” cost is $P_i$ and Yan uses the optimal drawing strategy.

1
7
1 2 10
1 3 10
2 4 5
2 5 10
3 6 10
3 7 20
2
10
100

90
100

Hint

Sample 1 Explanation

In the sample test, Yan plans to draw only one tree. For this tree, there are two possible values of $P$.

Example 1: $P_1 = 10$

The optimal strategy is to call two additional friends:

• Yan himself walks along the path $1 - 2 - 4 - 2 - 5$;
• Then he calls “Friend 1” to continue drawing starting from vertex 1;
• “Friend 1” walks along the path $1 - 3 - 7$;
• Next, “Friend 1” calls “Friend 2” to continue drawing starting from vertex 3;
• “Friend 2” walks along the path $3 - 6$.

The final score is:
$L + k \times P = (30 + 30 + 10) + 2 \times 10 = 90$
(Note: even if an edge has already been drawn, as long as it is traversed again, its length is still added to the final result.)

Example 2: $P_2 = 100$

Since calling friends is too expensive, Yan chooses to finish drawing the whole tree by himself. It can be proven that in this case, the minimum score he can achieve is $100$.

Constraints

• $1 \le T \le 5$
• $1 \le N \le 10^5$
• $1 \le Q \le 10^5$
• $1 \le l_i \le 10^9$
• $1 \le P_i \le 10^9$

The total number of queries over all testdata does not exceed $10^5$.

Subtasks

You can get the score of a subtask only if you pass all test points of that subtask.

Translation completed by Qwen3.5-397B-A17B.

Translated by ChatGPT 5