很久以前,真空吸尘器 Zhora 发现了一个装有坚果的大容器,该容器由一棵具有 $$$n$$$ 顶点的树表示。最初,在第 $$$i$$$ 个顶点中,有 $$$a_i$$$ 坚果。吸尘器佐拉最喜欢吃坚果,所以他决定把所有坚果都吃掉。
为了节省电力,吸尘器可以预先重新排列容器中的坚果。 Zhora 可以选择树的一个顶点 $$$v$$$,并且对于每个顶点 $$$u \ne v$$$, 非增加 路径$$$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, \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$$$。
输出
对于每个测试用例,输出吃掉所有坚果所需的最小电量单位。
示例
输入复制
64 1 11 1 1 11 22 32 45 1 1001 1 1 1 11 22 33 44 55 9 104 8 0 8 41 32 33 43 54 1 40 3 1 12 13 14 35 21 930 0 64 4 872 13 14 35 14 5 82 3 0 84 32 33 1
输出复制
210240627024
注意
在第一个测试用例中,最好将移动操作应用于顶点$$$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$$$电单位。