这是问题的困难版本。版本之间的区别在于,在这个版本中,$$$q \le 250\,000$$$。只有解决了该问题的所有版本,您才能破解。
给你一棵有 $$$n$$$ 个顶点的树,其中每个顶点的编号从 $$$1$$$ 到 $$$n$$$。每条边也被分配一个正整数权重 $$$w_1, w_2, \ldots, w_{n-1}$$$ 。
A 胜利着色 是将每个顶点着色为两种颜色: 红色 和 黄色,其中至少应有一个红色顶点(对应于 T1 队的符号)。
假设有一个 非负 分配给每个顶点的整数权重 $$$x_1, x_2, \ldots, x_n$$$。胜利着色的成本定义为所有红色顶点的权重之和,加上连接不同颜色(红色和黄色之间)顶点的所有边的权重之和。我们将 $$$f([x_1, x_2, \ldots, x_n])$$$ 定义为所有胜利着色的最小可能成本。
Gumayusi 考虑了计算 $$$f([x_1, x_2, \ldots, x_n])$$$ 的问题,给定序列 $$$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$$$。
输出
对于每个 $$$q$$$ 查询,输出以行分隔的答案。
示例
输入复制
253 5 102 3 43 1 103 4 25283211172321 2 311
输出复制
881082142661
注意
以下列表显示了第一个测试用例的每个查询的可能最佳分配:
- $$$[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]$$$