#215911. [Bulgarian NOI 2024] 树 / Tree

扬非常热爱计算机科学，尤其是图论。因此，他每天在学校都会画一棵树，并且努力避免将笔从纸上抬起。

每天，他都会构思一棵包含 个顶点的树，并从根节点开始绘制它。每条连接顶点 和 的边都有长度 。他从根出发，沿着边移动，不抬笔，并希望至少经过每个顶点和每条边一次。由于独自画图对扬来说已经非常无聊，他决定邀请朋友帮忙。具体方式如下：当他在树上某个顶点完成绘制后，可以召唤一位朋友前来协助——该朋友必须从当前所在的顶点开始继续绘制，同样遵守“不抬笔”的限制。

扬最好的朋友阿蒂娜总是用敏锐的目光观察他的游戏。她根据公式 为每幅画打分，其中 是扬和他的朋友们在纸上绘制的总路径长度（单位：厘米）， 是扬召唤的朋友总数，而 是“呼叫朋友”的费用——这个费用由扬在开始绘图前自行选定。请注意，如果某条边被多次遍历（即经过多次），其长度会在 中被重复计算（见示例 1）。

为了让阿蒂娜尽可能高兴，扬希望选择一个价格 ，使得她的评分尽可能小。但由于作业繁重，他向你求助。对于每一天，他都设想了不同的“呼叫朋友”费用值 ，并想知道在最优绘图策略下，阿蒂娜可能给出的最小评分是多少。

标准输入的第一行读入整数 —— 扬计划绘制的树的总数。随后依次给出每棵树的描述，以及你需要为扬解答的不同“呼叫朋友”费用值：

• 对于每棵树：第一行输入 —— 树中顶点的数量。
• 接下来 行，每行包含三个整数 ，分别表示连接两个顶点的一条边的端点及其长度。
• 然后输入一个整数 —— 表示你需要处理的“呼叫朋友”费用的不同取值个数。
• 最后 行，每行一个整数 ，代表第 种费用的具体数值。

对于每一幅画（即每棵树），输出 个数字 —— 分别对应在“呼叫朋友”费用为 时，扬通过最优绘图策略所能获得的、由阿蒂娜给出的最小评分。

样例输入 1

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

样例输出 1

90
100

样例 1 解释

在样例测试中，扬只计划绘制一棵树。对于这棵树，存在两种可能的 值。

示例 1：

此时最优策略是召唤两位额外的朋友协助：

• 扬本人将沿路径 行走；
• 随后他召唤“朋友 1”，从顶点 1 开始继续绘制；
• “朋友 1”将沿路径 行走；
• 接着，“朋友 1”再召唤“朋友 2”，从顶点 3 开始继续绘制；
• “朋友 2”将沿路径 行走。

最终评分为：

（请注意：即使某条边已被画过，只要再次经过它，其长度仍会累加到最终结果中。）

示例 2：

由于召唤朋友的代价过高，扬选择独自完成整棵树的绘制。可以证明，在这种情况下，他能达到的最小评分为 。

限制条件

所有测试数据中查询请求的总数不超过 。

子任务

只有当成功通过某子任务所对应的所有测试点时，才能获得该子任务的分数。

翻译由 Qwen3.5-397B-A17B 完成