CF2152H2.Victorious Coloring (Hard Version)

这是该问题的困难版本。该版本与其他版本的区别在于 $q \le 250\,000$。只有你解决了所有版本后，才可以对本题进行 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 感到满意，但还存在一个严重问题——这个问题没有任何询问，对于任何不是“坏的”题目来说是不可接受的。因此，他给这个问题增加了询问。每给定一个 $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 250\,000$）——询问次数。

接下来的 $q$ 行，每行一个整数 $l_i$（$1 \leq l_i \leq 10^9$），为第 $i$ 个询问参数。保证所有测试用例中 $n$ 的总和不超过 $250\,000$。

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

对于每个测试用例的每个询问，按行输出答案。

下面为第一个测试用例每个查询的最优赋值示例：

• $[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 翻译