← 返回题目列表

Codeforces · 2152/H1

H1. 胜利着色(简易版)

中文机器翻译题面 查看原题

这是问题的简单版本。版本之间的差异在于,在此版本中,$$$q \le 10$$$。只有解决了该问题的所有版本,您才能破解。

给你一棵有 $$$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 10$$$) — 查询数。

以下 $$$q$$$ 行包含单个整数 $$$l_i$$$ ($$$1 \leq l_i \leq 10^9$$$) — 第 $$$i$$$ 查询的参数。

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

请注意,$$$q$$$ 的总和没有明确的上限。

输出

对于每个 $$$q$$$ 查询,输出以行分隔的答案。

示例

输入
复制

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

输出
复制

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