B. Mensageiros
Uma rede de postos é ligada por estradas de mão dupla e forma uma árvore. É necessário percorrer cada estrada exatamente uma vez, no total.
Você pode contratar quantos mensageiros quiser. Contratar um mensageiro no posto custa . Ele começa nesse posto e percorre um caminho com pelo menos uma estrada, terminando em qualquer posto. Nenhuma estrada pode ser repetida por um mensageiro nem compartilhada entre mensageiros. Os caminhos podem compartilhar postos.
Determine o menor custo total para percorrer todas as estradas.
Input
A primeira linha contém (). A segunda contém inteiros (). Cada uma das próximas linhas contém dois inteiros (), indicando uma estrada. A rede dada é uma árvore.
Output
Imprima o menor custo total.
Samples
Sample 1
Input
4 10 1 2 3 1 2 1 3 1 4
Output
3
Um mensageiro sai do posto 2 e percorre 2–1–4. Outro sai do posto 3 e percorre 3–1. O custo total é 3.
Sample 2
Input
5 1 100 100 100 100 1 2 1 3 1 4 1 5
Output
4
Contrate quatro mensageiros no posto 1, um para cada estrada. Usar menos mensageiros não necessariamente reduz o custo.