这是问题的困难版本。两个版本之间的区别在于，在这个版本中，$q \le 250\,000$。只有解决了本题的所有版本，你才能进行 hack。

给你一棵拥有 $n$ 个顶点的树，顶点编号为 $1$ 到 $n$。每条边都被分配了一个正整数权重 $w_1, w_2, \dots, w_{n-1}$。

一个胜利染色是指将每个顶点染成两种颜色之一：红色或黄色，且必须有至少一个顶点被染成红色（对应 T1 战队的标志）。

假设每个顶点都被分配了一个非负整数权重 $x_1, x_2, \dots, x_n$。胜利染色的代价定义为所有红色顶点的权重之和，加上连接不同颜色（红色和黄色之间）顶点的所有边的权重之和。我们定义 $f([x_1, x_2, \dots, x_n])$ 为所有胜利染色中最小的可能代价。

Gumayusi 考虑了在给定序列 $x_1, x_2, \dots, x_n$ 的情况下计算 $f([x_1, x_2, \dots, x_n])$ 的问题。然而，这个问题对他来说太简单了，于是他设计了一个变种：给定一个整数 $l$，寻找一个非负整数顶点权重序列 $[x_1, x_2, \dots, x_n]$，使得 $f([x_1, x_2, \dots, x_n]) \ge l$，且总和 $\sum_{i=1}^n x_i$ 最小。

Gumayusi 很满意，但有一个严重的问题——这个问题没有任何询问，而这对于任何一个好题来说都是必不可少的。因此，他为这个问题添加了询问。对于作为询问给出的每个 $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 \le n$, $1 \le w_i \le 10^9$, $u_i \neq v_i$) — 表示一条连接顶点 $u_i$ 和 $v_i$ 且权重为 $w_i$ 的边。

保证这些边构成一棵树。

下一行包含一个整数 $q$ ($1 \le q \le 250\,000$) — 询问的数量。

接下来的 $q$ 行，每行包含一个整数 $l_i$ ($1 \le l_i \le 10^9$) — 第 $i$ 次询问的参数。

保证所有测试用例中 $n$ 的总和不超过 $250\,000$。

保证所有测试用例中 $q$ 的总和不超过 $250\,000$。

输出格式

对于每个 $q$ 次询问，输出一行表示答案。

样例

输入样例 1

2
5
3 5 10
2 3 4
3 1 10
3 4 2
5
28
32
11
17
23
2
1 2 3
1
1

输出样例 1

88
108
21
42
66
1

说明

以下列表显示了第一个测试用例中每个询问的一种可能的最优权重分配：

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