你,怪物杀手,想要杀死一群怪物。怪物在一棵有 $$$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$$$。