← 返回题目列表

Codeforces · 1988/D

D. 万能的怪物杀手

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

你,怪物杀手,想要杀死一群怪物。怪物在一棵有 $$$n$$$ 个顶点的树上。在编号为 $$$i$$$ ($$$1\le i\le n$$$) 的顶点上,有一个具有 $$$a_i$$$ 攻击点的怪物。您想与怪物战斗 $$$10^{100}$$$ 回合。

在每一轮中,按顺序发生以下情况:

1. 所有活着的怪物都会攻击你。你的生命值会减少所有活着的怪物的攻击点总和。
2. 你选择一些(可能是全部或没有)怪物并杀死它们。被杀死后,怪物将无法再进行任何攻击。

有一个限制:在一轮中,你不能杀死两个由边直接相连的怪物。

如果你选择最佳攻击哪些怪物,所有回合后你的最小生命值减量是多少?

输入

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

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1\le n\le 3\cdot 10^5$$$)。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1,\ldots,a_n$$$ ($$$1\le a_i\le 10^{12}$$$)。

以下 $$$n-1$$$ 行每行包含两个整数 $$$x,y$$$ ($$$1\le x,y\le n$$$),表示树上连接顶点 $$$x$$$ 和 $$$y$$$ 的边。

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

输出

对于每个测试用例,打印一个整数:可能的最小健康减量。

示例

输入 #1

3
1
1000000000000
5
47 15 32 29 23
1 2
1 3
2 4
2 5
7
8 10 2 3 5 7 4
1 2
1 4
3 2
5 3
6 2
7 5

输出 #1

1000000000000
193
57

注意

在第一个测试用例中,最佳操作顺序是:

- 第一轮:首先受到顶点$$$1$$$怪物的攻击,生命值减少$$$10^{12}$$$。然后杀死顶点$$$1$$$上的怪物。
- 在第 $$$10^{100}$$$ 轮的第二轮中:所有怪物都已被杀死,因此没有任何反应。

总生命值减量为 $$$10^{12}$$$。

在第二个测试用例中,最佳操作顺序是:

- 第一轮:首先受到顶点$$$1,2,3,4,5$$$怪物的攻击,生命值减少$$$47+15+32+29+23=146$$$。然后杀死顶点$$$1,4,5$$$上的怪物。
- 第二轮:首先受到顶点$$$2,3$$$怪物的攻击,生命值减少$$$15+32=47$$$。然后杀死顶点$$$2,3$$$上的怪物。
- 在第 $$$10^{100}$$$ 轮的第三轮中:所有怪物都已被杀死,因此没有任何反应。

生命值总减量为 $$$193$$$。

在第三个测试用例中,最佳操作顺序是:

- 第一轮:首先受到顶点$$$1,2,3,4,5,6,7$$$的怪物攻击,生命值减少$$$8+10+2+3+5+7+4=39$$$。然后杀死顶点$$$1,3,6,7$$$上的怪物。
- 第二轮:首先受到顶点$$$2,4,5$$$怪物的攻击,生命值减少$$$10+3+5=18$$$。然后杀死顶点$$$2,4,5$$$上的怪物。
- 在第 $$$10^{100}$$$ 轮的第三轮中:所有怪物都已被杀死,因此没有任何反应。

生命值总减量为 $$$57$$$。