P15846 [Bulgarian NOI 2024] 树 / Tree

扬非常热爱计算机科学，尤其是图论。因此，他每天在学校都会画一棵树，并且努力避免将笔从纸上抬起。 每天，他都会构思一棵包含 $N$ 个顶点的树，并从根节点开始绘制它。每条连接顶点 $a_i$ 和 $b_i$ 的边都有长度 $l_i$。他从根出发，沿着边移动，不抬笔，并希望至少经过每个顶点和每条边一次。由于独自画图对扬来说已经非常无聊，他决定邀请朋友帮忙。具体方式如下：当他在树上某个顶点完成绘制后，可以召唤一位朋友前来协助——该朋友必须从当前所在的顶点开始继续绘制，同样遵守“不抬笔”的限制。 扬最好的朋友阿蒂娜总是用敏锐的目光观察他的游戏。她根据公式 $L + k \times P$ 为每幅画打分，其中 $L$ 是扬和他的朋友们在纸上绘制的总路径长度（单位：厘米），$k$ 是扬召唤的朋友总数，而 $P$ 是“呼叫朋友”的费用——这个费用由扬在开始绘图前自行选定。请注意，如果某条边被多次遍历（即经过多次），其长度会在 $L$ 中被重复计算（见示例 1）。 为了让阿蒂娜尽可能高兴，扬希望选择一个价格 $P$，使得她的评分尽可能小。但由于作业繁重，他向你求助。对于每一天，他都设想了不同的“呼叫朋友”费用值 $P_i$，并想知道在最优绘图策略下，阿蒂娜可能给出的最小评分是多少。

标准输入的第一行读入整数 $T$ —— 扬计划绘制的树的总数。随后依次给出每棵树的描述，以及你需要为扬解答的不同“呼叫朋友”费用值： - 对于每棵树：第一行输入 $N$ —— 树中顶点的数量。 - 接下来 $N - 1$ 行，每行包含三个整数 $a_i, b_i, l_i$，分别表示连接两个顶点的一条边的端点及其长度。 - 然后输入一个整数 $Q$ —— 表示你需要处理的“呼叫朋友”费用的不同取值个数。 - 最后 $Q$ 行，每行一个整数 $P_i$，代表第 $i$ 种费用的具体数值。

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

### 样例 1 解释 在样例测试中，扬只计划绘制一棵树。对于这棵树，存在两种可能的 $P$ 值。 **示例 1：** $P_1 = 10$ 此时最优策略是召唤两位额外的朋友协助： - 扬本人将沿路径 $1 - 2 - 4 - 2 - 5$ 行走； - 随后他召唤“朋友 1”，从顶点 1 开始继续绘制； - “朋友 1”将沿路径 $1 - 3 - 7$ 行走； - 接着，“朋友 1”再召唤“朋友 2”，从顶点 3 开始继续绘制； - “朋友 2”将沿路径 $3 - 6$ 行走。 最终评分为： $L + k \times P = (30 + 30 + 10) + 2 \times 10 = 90$ （请注意：即使某条边已被画过，只要再次经过它，其长度仍会累加到最终结果中。） **示例 2：** $P_2 = 100$ 由于召唤朋友的代价过高，扬选择独自完成整棵树的绘制。可以证明，在这种情况下，他能达到的最小评分为 $100$。 ### 限制条件 - $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$ 所有测试数据中查询请求的总数不超过 $10^5$。 ### 子任务 | 子任务 | 分数 | $N$ | $Q; \sum Q$ | 额外限制条件 | |:------:|:----:|:-----------:|:----------------:|:------------------------:| | 1 | 5 | $\le 5$ | $= 1$ | | | 2 | 10 | $\le 10$ | $= 1$ | | | 3 | 15 | $\le 10^3$ | $= 1$ | | | 4 | 5 | $\le 10^5$ | $= 1$ | $l_i = 1, P_i = 10^9$ | | 5 | 20 | $\le 10^5$ | $\le 50$ | | | 6 | 5 | $\le 10^5$ | $\le 10^5$ | $a_i = 1$ | | 7 | 20 | $\le 10^5$ | $\le 10^4$ | | | 8 | 20 | $\le 10^5$ | $\le 10^5$ | | 只有当成功通过某子任务所对应的所有测试点时，才能获得该子任务的分数。 翻译由 Qwen3.5-397B-A17B 完成