A16558. Zhora the Vacuum Cleaner

从前，吸尘器 Zhora 发现了一个装坚果的大容器，这个容器可以用一棵 $n$ 个顶点的树来表示。初始时，第 $i$ 个顶点上有 $a_i$ 个坚果。吸尘器 Zhora 最喜欢吃坚果了，所以他决定吃掉所有的坚果。

为了节约电力，Zhora 可以预先重新布置容器中的坚果。Zhora 可以选择树中的一个顶点 $v$，对于每个不同于 $v$ 的顶点 $u$（按照路径 $uv$ 的长度非递增的顺序），如果 $u$ 中至少有一个坚果，那么 $u$ 中的一个坚果就会移动到 $u$ 的相邻顶点中离 $v$ 最近的那个顶点。这个操作需要消耗 $p$ 单位的电力。

执行若干次（可能为零次）这样的操作后，吸尘器 Zhora 从每个顶点吃掉所有坚果，每个有坚果的顶点会消耗 $q$ 单位的电力。

吃掉所有坚果所需的最小电力单位是多少？

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

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

在第一个测试用例中，最优方案是对顶点 $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$ 单位电力。