← 返回题目列表

Codeforces · 2189/F

F. 真空吸尘器 Zhora

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

很久以前,真空吸尘器 Zhora 发现了一个装有坚果的大容器,该容器由一棵具有 $$$n$$$ 顶点的树表示。最初,在第 $$$i$$$ 个顶点中,有 $$$a_i$$$ 坚果。吸尘器佐拉最喜欢吃坚果,所以他决定把所有坚果都吃掉。

为了节省电力,吸尘器可以预先重新排列容器中的坚果。 Zhora 可以选择树的一个顶点 $$$v$$$,并且对于每个顶点 $$$u \ne v$$$, 非增加 路径$$$uv$$$的长度顺序,如果$$$u$$$包含至少一个坚果,则$$$u$$$中的一个坚果移动到$$$u$$$的相邻顶点中距离$$$v$$$最近的顶点。此操作需要 $$$p$$$ 电力单位。

在执行了几次此类操作(可能没有)后,真空吸尘器 Zhora 吃掉了每个顶点的所有坚果,为每个包含坚果的顶点花费了 $$$q$$$ 电力单位。

吃完所有坚果至少需要多少电量?

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含三个整数 $$$n$$$、$$$p$$$ 和 $$$q$$$ ($$$2 \le n \le 10^5$$$, $$$0 \le p, q \le 10^6$$$) - 容器树中的顶点数以及类型 1 和 2 操作所需的电量,分别。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 10^6$$$) - 顶点中坚果的数量。

每个测试用例接下来的 $$$n - 1$$$ 行都包含两个整数 $$$u$$$ 和 $$$v$$$ ($$$1 \le u, v \le n, u \ne v$$$),表示从顶点 $$$u$$$ 到顶点 $$$v$$$ 的无向树边。保证给定的边形成一棵树。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^5$$$。

输出

对于每个测试用例,输出吃掉所有坚果所需的最小电量单位。

示例

输入
复制

6
4 1 1
1 1 1 1
1 2
2 3
2 4
5 1 100
1 1 1 1 1
1 2
2 3
3 4
4 5
5 9 10
4 8 0 8 4
1 3
2 3
3 4
3 5
4 1 4
0 3 1 1
2 1
3 1
4 3
5 21 93
0 0 64 4 87
2 1
3 1
4 3
5 1
4 5 8
2 3 0 8
4 3
2 3
3 1

输出
复制

2
102
40
6
270
24

注意

在第一个测试用例中,最好将移动操作应用于顶点$$$2$$$,然后吃掉顶点$$$2$$$上的所有$$$4$$$坚果,总共花费$$$1 + 1 = 2$$$电力单位。

在第二个测试用例中,最好对顶点$$$3$$$应用两次移动操作,然后吃掉顶点$$$3$$$上的所有$$$5$$$坚果,总共花费$$$1 + 1 + 100 = 102$$$电单位。

在第三个测试用例中,最好只吃掉顶点 $$$1,2,4,5$$$ 上的所有坚果,花费 $$$10 + 10 + 10 + 10 = 40$$$ 电力单位。

在第四个测试用例中,最好对顶点$$$2$$$应用两次移动操作,然后吃掉顶点$$$2$$$上的所有坚果,总共花费$$$6$$$电单位。