Divisão de Árvore

#183

Made by: Crazynds

100MB

0.1s

Dada uma árvore com $N$ nós, onde cada nó $i$ possui um valor $w_i$, você deve remover exatamente $K$ arestas, dividindo a árvore em $K+1$ subárvores (componentes conexas).

Minimize o valor máximo entre as somas dos pesos de todas as subárvores resultantes.

Input

A primeira linha contém dois inteiros $N$ e $K$ $(1 \le K < N \le 10^5,\ 1 \le w_i \le 10^9)$.

A segunda linha contém $N$ inteiros $w_i$.

As próximas $N-1$ linhas contêm dois inteiros $u$ e $v$, representando uma aresta da árvore.

Output

Imprima um único inteiro: o menor valor máximo possível de soma entre os $K+1$ componentes.

Input Example

Output Example

6 2
4 5 6 3 2 7
1 2
1 3
2 4
3 5
3 6

Explanation 1:
A árvore: ``` 1(4) / \ 2(5) 3(6) | / \ 4(3) 5(2) 6(7) ``` Removendo as arestas $1-3$ e $3-6$, obtemos os componentes: - $\{1, 2, 4\}$ com soma $4+5+3 = 12$ - $\{3, 5\}$ com soma $6+2 = 8$ - $\{6\}$ com soma $7$ Máximo $= 12$. Qualquer outra escolha de 2 arestas resulta em máximo $\ge 12$, portanto a resposta é $\mathbf{12}$.

27 20
81909 41336 18785 91924 65502 86099 52943 3621 40588 82983 52084 96339 78481 62146 26639 89569 83037 24602 90189 43853 94422 50564 6770 87584 99171 42093 58677
1 2
2 3
3 4
4 5
1 6
4 7
6 8
6 9
8 10
10 11
6 12
8 13
5 14
1 15
5 16
15 17
13 18
5 19
16 20
7 21
2 22
20 23
4 24
2 25
1 26
2 27