28896번 - Энергия 다국어

Злодею Ван Пелту срочно нужно зарядить свою игровую приставку. Для этих целей у него есть целый подземный лабиринт, содержащий источники энергии.

Лабиринт Ван Пелта состоит из $n$ комнат, пронумерованных целыми числами от $1$ до $n$. Некоторые пары комнат соединены между собой коридорами, по которым можно перемещаться в обоих направлениях.

Назовем путем между двумя комнатами $a$ и $b$ последовательность комнат $u_1, u_2, \dots, u_k$, где $u_1 = a$, $u_k = b$, а также для всех $1 \le i \le k - 1$ комнаты $u_i$ и $u_{i + 1}$ соединены коридором. Лабиринт Ван Пелта устроен так, что между любыми двумя комнатами есть ровно один путь. Иными словами, лабиринт представляет из себя дерево. Таким образом, в лабиринте есть ровно $n - 1$ коридор, соединяющий комнаты.

Так как в лабиринте темно и страшно, Ван Пелт не хочет идти туда сам. Зато у него есть $k$ ягуаров, каждого из которых он отправит в лабиринт за энергией. Для каждого ягуара Ван Пелт должен выбрать пару комнат (возможно, совпадающих), после чего ягуар отправится в лабиринт и пройдет по всем комнатам, лежащим на пути между выбранными комнатами (включая сами выбранные комнаты). Так как ягуары очень агрессивные животные, никакие два выбранных пути не должны содержать общих комнат, иначе ягуары могут подраться. Обратите внимание, что каждого ягуара Ван Пелт обязан отправить в лабиринт.

В каждой комнате лабиринта установлен источник энергии. Источник в комнате с номером $i$ содержит $a_i$ единиц энергии. Обратите внимание, что источник может содержать отрицательное количество энергии. Каждый ягуар, отправленный Ван Пелтом, заберет источники энергии во всех комнатах, по которым пройдет. Энергия, которую получит Ван Пелт для зарядки, равна суммарной энергии всех источников, которые заберут с собой ягуары.

Определите, какое максимальное количество энергии может получить Ван Пелт.

Первая строка входных данных содержит два целых числа $n$ и $k$ --- количество комнат в лабиринте Ван Пелта и количество ягуаров ($1 \le n \le 1000$, $1 \le k \le n$).

Вторая строка содержит $n$ чисел $a_i$ --- заряды источников энергии в комнатах ($-10^9 \le a_i \le 10^9$). Числа разделены пробелом.

Далее $n - 1$ строка содержит описание коридоров лабиринта. Каждая из этих строк содержит два числа $u_i$ и $v_i$ --- номера комнат, соединенных очередным коридором.

Выведите единственное целое число --- максимальное количество энергии, которое может получить Ван Пелт.

В тесте из условия Ван Пелт может отправить одного ягуара на путь между вершинами $3$ и $7$, а другого --- на путь между вершинами $5$ и $6$. Тогда ягуары обойдут комнаты с номерами $3$, $7$, $5$, $4$ и $6$, собрав $14$ единиц энергии.