F. Защита шерифа
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод
"Почему, мастер," сказал Маленький Джон, беря мешки и взвешивая их в руке, "вот блеск золота."

Народный герой Робин Гуд сильно беспокоит шерифа Ноттингема. Шериф знает, что Робин Гуд собирается атаковать его лагеря, и он хочет быть готовым.

Шериф Ноттингема построил лагеря с учетом стратегии, и поэтому есть ровно $$$n$$$ лагерей, пронумерованных от $$$1$$$ до $$$n$$$, и $$$n-1$$$ троп, каждая из которых соединяет два лагеря. Любой лагерь можно достичь из любого другого лагеря. Каждый лагерь $$$i$$$ изначально имеет $$$a_i$$$ золота.

Шериф может укрепить лагерь, вычитая ровно $$$c$$$ золота из каждого из его соседних лагерей и использовать это для строительства лучших защит для этого лагеря. Укрепление лагеря не изменяет его золото, только золото его соседей. Лагерь может иметь отрицательное количество золота.

После атаки Робина Гуда все лагеря, которые не были укреплены, будут уничтожены.

Какое максимальное количество золота шериф может сохранить в своих лагерях после атаки Робина Гуда, если он оптимально укрепляет свои лагеря?

Лагерь $$$a$$$ является соседним лагерем $$$b$$$, если и только если существует тропа, соединяющая $$$a$$$ и $$$b$$$. Только укрепленные лагеря учитываются в ответе, так как остальные будут уничтожены.

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

Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.

Каждый набор входных данных начинается с двух целых чисел $$$n$$$, $$$c$$$ ($$$1 \le n \le 2\cdot10^5, 1 \le c \le 10^9$$$) — количество лагерей и золота, взимаемого с каждого соседнего лагеря для укрепления.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1,a_2,\dots,a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$) — начальное золото каждого лагеря.

Затем следуют $$$n-1$$$ строк, каждая с целыми числами $$$u$$$, $$$v$$$ ($$$1 \le u, v \le n$$$, $$$u \ne v$$$) — что означает, что существует тропа между $$$u$$$ и $$$v$$$.

Сумма $$$n$$$ по всем наборам входных данных не превышает $$$2\cdot10^5$$$.

Гарантируется, что любой лагерь достижим из любого другого лагеря.

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

Выведите одно целое число, максимальное золото, которое шериф Ноттингема может сохранить в своих выживших лагерях после атаки Робина Гуда.

Пример
Входные данные
5
3 1
2 3 1
1 2
2 3
3 1
3 6 3
1 2
2 3
3 1
-2 -3 -1
1 2
2 3
6 1
5 -4 3 6 7 3
4 1
5 1
3 5
3 6
1 2
8 1
3 5 2 7 8 5 -3 -4
7 3
1 8
4 3
3 5
7 6
8 7
2 1
Выходные данные
3
8
0
17
26
Примечание

В первом наборе входных данных оптимально укрепить второй лагерь. Конечное золото в каждом лагере составляет $$$[1,3,0]$$$.

Во втором наборе входных данных оптимально укрепить все лагеря. Конечное золото в каждом лагере составляет $$$[2,4,2]$$$.

В третьем наборе входных данных оптимально не укреплять ни один лагерь.