题目描述

你，怪物猎人，想要消灭一群怪物。这些怪物分布在一棵有 $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$。

输出格式

对于每个测试用例，输出一个整数，表示你生命值减少的最小可能值。

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

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