CF2189F.Zhora the Vacuum Cleaner

Once upon a time, Zhora the Vacuum Cleaner found a big container with nuts that is represented by a tree with $n$ vertices. Initially, in the $i$-th vertex, there are $a_i$ nuts. What Zhora the Vacuum Cleaner likes most is eating nuts, so he decided to eat all the nuts.

To save electricity, the vacuum cleaner can rearrange the nuts in the container beforehand. Zhora can choose a vertex $v$ of the tree, and for every vertex $u \ne v$, in non-increasing order of the length of path $uv$, if $u$ contains at least one nut, one nut from $u$ moves into the closest vertex to $v$ among $u$'s adjacent vertices. This operation requires $p$ electricity units.

After performing several such operations (possibly none), Zhora the Vacuum Cleaner eats all the nuts from every vertex, spending $q$ electricity units per every vertex that contains nuts.

What is the minimum amount of electricity units required to eat all the nuts?

从前，吸尘器卓拉发现了一个装满坚果的大容器，该容器被表示为一棵含有 $n$ 个顶点的树。初始时，第 $i$ 个顶点上有 $a_i$ 颗坚果。卓拉最喜爱的事情就是吃坚果，因此他决定吃掉所有坚果。

为了节省电量，吸尘器可以在吃坚果之前重新分配容器中的坚果。卓拉可以选择树上的一个顶点 $v$，然后对每个顶点 $u \ne v$，按路径 $uv$ 的长度非递增顺序处理：若 $u$ 中至少有一颗坚果，则从 $u$ 中取出一颗坚果，并将其移入 $u$ 的所有邻接顶点中距离 $v$ 最近的那个顶点。执行一次这样的操作需要消耗 $p$ 单位电量。

在执行若干次（可能为零次）上述操作后，卓拉将吃掉每个顶点上的全部坚果，对每个含有坚果的顶点额外消耗 $q$ 单位电量。

吃掉所有坚果所需的最少电量是多少？

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains three integers $n$, $p$, and $q$ ($2 \le n \le 10^5$, $0 \le p, q \le 10^6$) — the number of vertices in the container's tree and the required amounts of electricity for operations of types 1 and 2, respectively.

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le 10^6$) — the quantities of nuts in the vertices.

Each of the next $n - 1$ lines of each test case contains two integers $u$ and $v$ ($1 \le u, v \le n, u \ne v$), representing an undirected tree edge from vertex $u$ to vertex $v$. It is guaranteed that the given edges form a tree.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $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$。

For each test case, output the minimum amount of electricity units required to eat all the nuts.

对于每个测试用例，输出吃完所有坚果所需的最少电量单位数。

In the first test case, it is best to apply the movement operation to vertex $2$, and then eat all the $4$ nuts from vertex $2$, spending $1 + 1 = 2$ electricity units in total.

In the second test case, it is best to apply the movement operation twice to vertex $3$, and then eat all the $5$ nuts from vertex $3$, spending $1 + 1 + 100 = 102$ electricity units in total.

In the third test case, it is best just to eat all the nuts from vertices $1,2,4,5$, spending $10 + 10 + 10 + 10 = 40$ electricity units.

In the fourth test case, it is best to apply the movement operation twice to vertex $2$, and then eat all the nuts from vertex $2$, spending $6$ electricity units in total.

在第一个测试用例中，最优策略是将移动操作应用于顶点 $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$ 单位电量。