Великая Подземная Линейная Сеть — это огромная транспортная система, соединяющая все уголки Генсокио. Момойо заметила, что структура сети напоминает дерево$$$^{\text{∗}}$$$. Она не могла не задуматься о том, как наиболее эффективно разобрать это дерево.
Дано дерево из $$$n$$$ вершин, где вершина $$$i$$$ имеет вес $$$a_i$$$. Выберите простой путь ровно из $$$k$$$ рёбер и удалите все рёбра на нём. Это разобьёт дерево на $$$k+1$$$ связных компонент, вес каждой из которых равен сумме весов её вершин. Требуется максимизировать минимальный вес компоненты, либо вывести $$$-1$$$, если не существует простого пути ровно из $$$k$$$ рёбер.
$$$^{\text{∗}}$$$Деревом называется связный граф без циклов.
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$k$$$ ($$$1 \le k \le n-1$$$, $$$2 \le n \le 2 \cdot 10^5$$$).
Во второй строке содержится $$$n$$$ целых чисел, где $$$i$$$-е число обозначает $$$a_i$$$ ($$$1 \le a_i \le 10^9$$$).
Следующие $$$n-1$$$ строк содержат по два целых числа $$$u$$$ и $$$v$$$, обозначающие ребро дерева.
Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$2\cdot 10^5$$$.
Для каждого набора входных данных выведите максимальный возможный минимальный вес компоненты, либо $$$-1$$$, если такого пути не существует.
54 11 2 3 41 22 33 44 21 2 3 41 22 33 44 31 2 3 41 22 33 47 27 1 3 2 2 4 31 22 32 42 55 65 74 31 2 3 41 21 31 4
4316-1
В первом наборе входных данных рассмотрите путь $$$3\to4$$$. Удаление этого пути даёт компоненты весов $$$6$$$ и $$$4$$$.
В четвёртом наборе входных данных возьмите путь $$$1\to2\to5$$$. Удаление этого пути даёт компоненты весов $$$7$$$, $$$6$$$ и $$$9$$$.
| Codeforces Round 1098 (Div. 2) |
|---|
| Закончено |
