题目描述

扬（Yan）非常喜欢信息学，尤其喜欢图论。因此，他每天在学校里都会画一棵树，并且尽量在绘制过程中不把笔从纸上抬起来。

每天，他都会想出一棵有 $N$ 个点的树，并从树的根开始绘制。每条边连接顶点 $a_i$ 和 $b_i$，长度为 $l_i$。从根开始后，他沿着树边移动，在整个过程中不抬笔，并希望经过所有顶点和所有边至少一次。

后来，扬觉得一个人画太无聊了，于是决定让朋友们帮忙。规则如下：

• 当树上的某个顶点已经被画到之后，扬可以叫来一个朋友；
• 这个朋友从该顶点开始继续画；
• 每个人在自己的绘制过程中也都不能抬笔。

扬最好的朋友阿西娜（Athena）会给每次绘制打分。评分公式为：

其中：

• $L$ 表示扬和所有朋友在纸上画过的总长度；
• $k$ 表示扬叫来的朋友总数；
• $P$ 表示“呼叫一个朋友”的费用，由扬在开始作画前选定。

注意：如果某条边被重复经过多次，那么它的长度会被重复计入 $L$ 中。

扬希望让阿西娜给出的分数尽可能小。对于每一天，他都会考虑若干不同的费用 $P_i$，并想知道：当“呼叫朋友”的费用为 $P_i$ 时，最小可能得分是多少。

输入格式

第一行一个整数 $T$，表示测试组数。

对于每组测试：

• 第一行一个整数 $N$，表示树的节点数。
• 接下来 $N-1$ 行，每行三个整数 $a_i, b_i, l_i$，表示一条边的两个端点及其长度。
• 接下来一行一个整数 $Q$，表示需要回答的不同费用个数。
• 接下来 $Q$ 行，每行一个整数 $P_i$，表示一次“呼叫朋友”的费用。

输出格式

对于每组测试，输出 $Q$ 行，每行一个整数，表示当费用为对应的 $P_i$ 时，扬能够得到的最小分数。

数据范围

• $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$
• 所有测试数据中，$Q$ 的总和不超过 $10^5$

子任务

只有通过某个子任务中的所有测试点，才能获得该子任务的全部分数。

样例输入

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

样例说明

样例中只有 $1$ 棵树，需要回答两种不同的费用 $P$。

情况 1：$P_1=10$

最优方案是再叫来 2 个朋友帮忙：

• 扬先走路径：$1 \to 2 \to 4 \to 2 \to 5$；
• 然后他在顶点 $1$ 叫来朋友 1；
• 朋友 1 走路径：$1 \to 3 \to 7$；
• 接着他们在顶点 $3$ 再叫来朋友 2；
• 朋友 2 走路径：$3 \to 6$。

于是总绘制长度为：

朋友数为：

总得分为：

注意，即使某条边之前已经被画过，只要再次经过，它的长度仍然会再次计入答案。

情况 2：$P_2=100$

由于叫朋友的代价太高，最优方案是由扬一个人完成整棵树的绘制。

可以证明，此时最小得分为：