题目描述

有一棵 $n$ 个节点的有根树。节点编号从 $1$ 到 $n$（含两端），其中节点 $1$ 是根节点。一开始所有 $n$ 个节点都是白色的，您需要将所有节点染成黑色。

为了帮助您达成目标，我们提供 $n$ 种操作，编号从 $0$ 到 $(n - 1)$（含两端）。操作 $i$（$0 \le i \le n - 1$）需要您首先选择一个节点 $u$，之后将所有满足以下条件的节点 $v$ 染成黑色：

• 节点 $v$ 在以 $u$ 为根的子树里，也就是说 $u = v$ 或 $u$ 是 $v$ 的祖先节点。
• 节点 $u$ 与 $v$ 之间的距离恰为 $i$。节点 $u$ 与 $v$ 之间的距离指的是从 $u$ 走到 $v$ 需要经过的最少边数。

执行一次操作 $i$ 的代价是 $a_i$。一个节点可以被多次染色，所有操作都可以被执行任意次。求将所有节点染成黑色的最小总代价。

输入格式

有多组测试数据。第一行输入一个整数 $T$ 表示数据组数，对于每组测试数据：

第一行输入一个整数 $n$（$2 \le n \le 10^5$）表示树的大小。

第二行输入 $n$ 个整数 $a_0, a_1, \cdots, a_{n-1}$（$1 \le a_i \le 10^9$），其中 $a_i$ 表示执行一次操作 $i$ 的代价。

对于接下来 $(n - 1)$ 行，第 $i$ 行输入两个整数 $u_i$ 和 $v_i$（$1 \le u_i, v_i \le n$，$u_i \neq v_i$）表示有一条边连接节点 $u_i$ 和 $v_i$。

保证所有数据 $n$ 之和不超过 $3 \times 10^5$。

输出格式

每组数据输出一行一个整数，表示染黑整棵树的最小总代价。

3
4
10 15 40 1
1 2
2 3
2 4
5
10 5 1 100 1000
1 2
2 3
2 4
4 5
4
1000 200 10 8
1 2
2 3
3 4

35
17
1218

提示

第一组样例数据如下所示。答案是 $15 + 10 + 10 = 35$。

:::align{center} :::

第二组样例数据如下所示。答案是 $5 + 10 + 1 + 1 = 17$。

:::align{center} :::