F. Динамические значения и максимальный счёт
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дано дерево$$$^{\text{∗}}$$$ с $$$n$$$ вершинами, пронумерованными от 1 до $$$n$$$, где каждая вершина $$$i$$$ имеет начальное значение $$$a_i$$$. Вы выполняете $$$k$$$ операций. Изначально ваш счёт равен $$$0$$$. В каждой операции:

  1. Выберите вершину $$$r$$$ и сделайте $$$r$$$ корнем дерева.
  2. Добавьте текущее значение $$$r$$$ к счёту и установите значение $$$r$$$ в $$$0$$$.
  3. Для каждой вершины $$$u$$$, которая не является листом$$$^{\text{†}}$$$, найдите листья в поддереве$$$^{\text{‡}}$$$ вершины $$$u$$$, которые находятся на максимальном расстоянии от $$$u$$$. Среди них выберите ту, у которой наименьший индекс, обозначив её как назначение для $$$ u $$$. Добавьте текущее значение $$$u$$$ к назначению и установите значение $$$u$$$ в $$$0$$$.
Найдите максимальный возможный счёт.

$$$^{\text{∗}}$$$Деревом называется связный граф без циклов.

$$$^{\text{†}}$$$Листом называется любая вершина, у которой нет детей.

$$$^{\text{‡}}$$$Поддеревом вершины $$$v$$$ называется подграф, состоящий из вершины $$$v$$$, всех ее потомком, и всех ребер между ними.

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10 ^ 4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$k$$$ ($$$1 \le k \le n \le 3 \cdot 10^5$$$).

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

Каждая из следующих $$$n-1$$$ строк содержит два целых числа $$$u$$$ и $$$v$$$, обозначающих ребро, соединяющее вершины $$$u$$$ и $$$v$$$. Гарантируется, что заданные ребра образуют дерево.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$3\cdot 10 ^ 5$$$.

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

Для каждого набора входных данных выведите целое число — максимальный возможный счёт.

Пример
Входные данные
7
5 4
19 20 39 81 2
1 2
1 3
2 4
2 5
5 3
12 21 39 8 21
1 2
1 3
3 4
2 5
5 2
129 216 32 83 221
1 2
1 3
3 4
4 5
5 3
15 15 15 15 15
1 2
1 3
1 4
1 5
1 1
1
2 1
1 1000000000
1 2
7 2
8 3 5 7 9 1 6
4 3
7 5
5 2
2 3
3 6
6 1
Выходные данные
161
101
681
60
1
1000000000
32
Примечание

В первом наборе входных данных:

  1. Выберите вершину $$$1$$$ в качестве корня. Добавьте $$$a_1 = 19$$$ к счёту и установите $$$a_1 = 0$$$.

    После установки корня дерева в $$$1$$$, для каждой не-листовой вершины $$$u$$$ переместите её значение к листу в её поддереве, который находится дальше всего от $$$u$$$ (разрешая ничьи по наименьшему индексу). При этом корне:

    • Значение вершины $$$2$$$ передаётся вершине $$$4$$$, так что $$$a_2$$$ становится $$$0$$$, а $$$a_4$$$ становится $$$101$$$.
    • Значения вершин $$$3$$$, $$$4$$$ и $$$5$$$ остаются на своих местах согласно правилу.

  2. Выберите вершину $$$3$$$ в качестве корня. Добавьте $$$a_3 = 39$$$ к счёту и установите $$$a_3 = 0$$$.

    После перераспределения при этом корне значения вершин $$$4$$$ и $$$5$$$ остаются на своих местах.

  3. Выберите вершину $$$4$$$ в качестве корня. Добавьте $$$a_4 = 101$$$ к счёту и установите $$$a_4 = 0$$$.

    После перераспределения значение в вершине $$$5$$$ остаётся неизменным.

  4. Выберите вершину $$$5$$$ в качестве корня. Добавьте $$$a_5 = 2$$$ к счёту и установите $$$a_5 = 0$$$.

Полученный счёт равен $$$19 + 39 + 101 + 2 = 161$$$.

В шестом наборе входных данных выберите вершину $$$2$$$ в качестве корня. Добавьте её значение к счёту, получив $$$1\,000\,000\,000$$$.