CFCF2189F.Zhora the Vacuum Cleaner

省选/NOI-

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

从前，吸尘器 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$ 。

输出格式

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

输入输出样例

输入#1

6
4 1 1
1 1 1 1
1 2
2 3
2 4
5 1 100
1 1 1 1 1
1 2
2 3
3 4
4 5
5 9 10
4 8 0 8 4
1 3
2 3
3 4
3 5
4 1 4
0 3 1 1
2 1
3 1
4 3
5 21 93
0 0 64 4 87
2 1
3 1
4 3
5 1
4 5 8
2 3 0 8
4 3
2 3
3 1

输出#1

说明/提示

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

首页