CF2152H1.Victorious Coloring (Easy Version)

This is the easy version of the problem. The difference between the versions is that in this version, $q \le 10$. You can hack only if you solved all versions of this problem.

You are given a tree with $n$ vertices, where each vertex is numbered from $1$ to $n$. Each edge is assigned a positive integer weight $w_1, w_2, \ldots, w_{n-1}$ as well.

A victorious coloring is a coloring of each vertex into two colors: red and yellow, where there should be at least one vertex colored in red (corresponding to the symbol of team T1).

Suppose that there is a nonnegative integer weight $x_1, x_2, \ldots, x_n$ assigned to each vertex. The cost of the victorious coloring is defined as the sum of the weights of all red vertices, plus the sum of the weights of all edges that connect vertices of different colors (between red and yellow). We define $f([x_1, x_2, \ldots, x_n])$ as the minimum possible cost for all victorious colorings.

Gumayusi considered the problem of computing $f([x_1, x_2, \ldots, x_n])$, given the sequence $x_1, x_2, \ldots, x_n$. However, this problem was too easy for him, so he devised a variation: Given an integer $l$, find a sequence of nonnegative integer vertex weights $[x_1, x_2, \ldots, x_n]$ such that $f([x_1, x_2, \ldots, x_n]) \ge l$ and the total sum $\sum_{i=1}^n x_i$ is minimized.

Gumayusi was satisfied, but there was a serious issue — this problem doesn't have any queries, which is a necessary component for any problem that isn't bad. So, he added queries to this problem. For each $l$ given as a query, you must find the corresponding minimum possible sum of vertex weights.

这是该问题的简单版本。两个版本的区别在于，在此版本中，$q \le 10$。仅当您解决了该问题的所有版本后，才可进行 Hack。

给定一棵包含 $n$ 个顶点的树，各顶点编号为 $1$ 至 $n$。每条边均被赋予一个正整数权重 $w_1, w_2, \ldots, w_{n-1}$。

一种胜利染色（victorious coloring）是指将每个顶点染成两种颜色之一：红色与黄色，且至少有一个顶点被染成红色（对应队伍 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 对此感到满意，但存在一个严重问题——该问题不含任何查询（queries），而查询是任何非劣质题目所必需的组成部分。因此，他向该问题添加了查询：对每个作为查询给出的 $l$，您必须求出对应的顶点权重最小可能总和。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line contains an integer $n$ ($2 \le n \le 250\,000$) — the number of vertices.

The following $n-1$ lines contain three integers $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$) — indicating an edge connecting the vertices $u_i$ and $v_i$ with weight $w_i$.

It is guaranteed that the edges form a tree.

The next line contains an integer $q$ ($1 \le q \le 10$) — the number of queries.

The following $q$ lines contain a single integer $l_i$ ($1 \leq l_i \leq 10^9$) — the parameters of the $i$-th query.

It is guaranteed that the sum of $n$ over all test cases does not exceed $250\,000$.

Note that there is no explicit upper bound on the sum of $q$.

每个测试包含多个测试用例。第一行包含测试用例数量 $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$ 之和没有显式的上界限制。

For each of the $q$ queries, output the answer separated by lines.

对于每个 $q$ 个查询，输出对应的答案，各答案之间用换行符分隔。

The following list shows the possible optimal assignments for each query in the first test case:

• $[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]$

以下列表展示了第一个测试用例中每个查询的可能最优分配方案：

• $[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]$