F. Жора-Пылесос
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Как-то раз Жора-Пылесос нашёл большой контейнер с гайками, который представляется в виде дерева на $$$n$$$ вершинах, изначально в $$$i$$$-й вершине лежит $$$a_i$$$ гаек. Больше всего на свете Жора любит есть гайки, поэтому он решил съесть все гайки из контейнера.

Чтобы потратить меньше электричества, пылесос может предварительно переместить гайки в контейнере. Жора может выбрать вершину дерева $$$v$$$, и для каждой вершины $$$u \ne v$$$, в порядке невозрастания длины пути $$$uv$$$, если в $$$u$$$ есть хотя бы одна гайка, одна гайка из $$$u$$$ перемещается в вершину, ближайшую к $$$v$$$ среди смежных с $$$u$$$. На эту операцию уходит $$$p$$$ единиц электричества.

После выполнения нескольких таких операций (возможно, ни одной), Жора-Пылесос съедает все гайки из каждой вершины, тратя на каждую вершину, в которой есть гайки, $$$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$$$.

Выходные данные

Для каждого набора входных данных выведите минимальное количество единиц электричества, нужное, чтобы съесть все гайки.

Пример
Входные данные
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
Выходные данные
2
102
40
6
270
24
Примечание

В первом наборе входных данных наиболее выгодно применить операцию перемещения к вершине $$$2$$$, а затем съесть все $$$4$$$ гайки из вершины $$$2$$$, суммарно потратив $$$1 + 1 = 2$$$ единицы энергии.

Во втором наборе входных данных наиболее выгодно дважды применить операцию перемещения к вершине $$$3$$$, а затем съесть все $$$5$$$ гаек из вершины $$$3$$$, суммарно потратив $$$1 + 1 + 100 = 102$$$ единицы энергии.

В третьем наборе входных данных наиболее выгодно сразу съесть все гайки из вершин $$$1,2,4,5$$$, потратив $$$10 + 10 + 10 + 10 = 40$$$ единиц энергии.

В четвёртом наборе входных данных наиболее выгодно дважды применить операцию перемещения к вершине $$$2$$$, а затем съесть все гайки из вершины $$$2$$$, суммарно потратив $$$6$$$ единиц энергии.