CF2152H1 Victorious Coloring (Easy Version)

这是本题的简单版本。不同版本的区别在于本版本中 $q \le 10$。只有当你解决了所有版本的问题后，才能对题目进行 hack。 给定一棵有 $n$ 个顶点的树，每个顶点从 $1$ 到 $n$ 编号。每条边分配有正整数权值 $w_1, w_2, \ldots, w_{n-1}$。 “胜利染色”指的是将每个顶点染成红色或黄色两种颜色，其中至少要有一个顶点被染成红色（代表队伍 T1 的标志）。 假设每个顶点被分配了一个非负整数权值 $x_1, x_2, \ldots, x_n$。则“胜利染色”的代价定义为所有红色顶点的权值之和，再加上连接红黄两种颜色顶点之间的所有边的权值之和。我们记 $f([x_1, x_2, \ldots, x_n])$ 为所有胜利染色下的最小可能代价。 Gumayusi 思考了对于给定序列 $x_1, x_2, \ldots, x_n$，如何计算 $f([x_1, x_2, \ldots, x_n])$。但这个问题对他而言太简单了，于是他又提出了一个变体：给定整数 $l$，请找到一种非负整数顶点权值序列 $[x_1, x_2, \ldots, x_n]$，使得 $f([x_1, x_2, \ldots, x_n]) \ge l$，且 $\sum_{i=1}^n x_i$ 尽可能小。 Gumayusi 很满意，但还存在一个严重问题——这个问题没有任何查询（query），而没有查询的问题在他看来都不是好题。所以，他为这个问题增加了查询。对于每个给定的 $l$，你需要输出对应的最小可能顶点权值之和。

每个测试点包含多组测试用例。第一行包含测试用例个数 $t$（$1 \le t \le 10^4$）。每组测试用例格式如下： 第一行包含一个整数 $n$（$2 \le n \le 250\,000$），表示顶点数。 接下来的 $n-1$ 行，每行包含三个整数 $u_i, v_i, w_i$（$1 \le u_i, v_i \leq n, 1 \le w_i \le 10^9, u_i \neq v_i$），表示在 $u_i$ 和 $v_i$ 之间有一条权值为 $w_i$ 的边。 保证所有边形成一棵树。 下一行包含一个整数 $q$（$1 \le q \le 10$），表示查询个数。 接下来的 $q$ 行，每行包含一个整数 $l_i$（$1 \leq l_i \leq 10^9$），表示第 $i$ 个查询的参数。 保证所有测试用例中 $n$ 的总和不超过 $250\,000$。 注意，$q$ 的总和没有明确的上界。

对于每个查询，输出一行答案。

下表展示了第一个测试用例中每个查询的可能最优赋值： - $[18,24,2,26,18]$ - $[22,28,6,30,22]$ - $[4,7,0,9,1]$ - $[7,13,0,15,7]$ - $[13,19,0,21,13]$ 由 ChatGPT 5 翻译