In Hackerville există un parc special. Acest parc are N copaci uniţi prin N-1 poteci, astfel încât se poate ajunge de la un copac la oricare alt copac mergând numai pe poteci.
O potecă uneşte doi copaci.
Mulţi bătrâni s-au plâns conducerii oraşului că parcul este prea întunecat, iar conducerea a hotărât să ia măsuri.
Hackerville fiind condus de un geniu al programării, acesta a decis să taie k copaci, dar nu la întamplare.
El vrea să taie k copaci astfel încât drumul total parcurs de un muncitor pentru tăierea lor să fie minim.
Deoarece conducătorul oraşului este plecat la o conferinţă importantă, el va roagă pe voi să îl ajutaţi.
Copacii sunt numerotaţi de la 1 la N.
Cerinţă
Cerinţa pe care conducătorul oraşului v-a dat-o este să aflaţi numărul minim de poteci pe care trebuie să
le parcurgă un muncitor pentru a tăia k copaci.
Date de intrare
Fişierul de intrare copaci3.in contine pe prima linie două numere N şi M reprezentând numărul de copaci din parc, respectiv numărul de interogări. Pe următoarele N-1 linii vor fi câte două numere, x şi y reprezentând numerele a doi copaci care sunt uniţi de o potecă. Pe următoarele M linii va fi câte un număr natural ki reprezentând numărul de copaci pe care conducătorul oraşului vrea să îi taie la interogarea i (1 <= i <= M).
Date de ieşire
Fişierul de ieşire copaci3.out va conţine M linii. Pe linia i dintre cele M (1<=i<=M) va fi scris un număr reprezentând costul minim pentru a taia cei ki copaci din interogarea i.
Restricţii
1 <= N, M <= 100 000
1 <=
k <= N
Pentru 40% din teste 1 <=
N <= 1 000
Exemple
copaci3.in
copaci3.out
Explicatie
4 2
3 2
1 2
4 2
2
4
1
4
Sunt 4 copaci in parc. Avem 2 interogări.
Pentru k=2 muncitorul parcurge traseul:
1->2, astfel el a tăiat 2 copaci făcând 1 drum.
Pentru k=4 muncitorul parcurge traseul:
4->2->3->2->1, astfel el a tăiat 4 copaci făcând 4 drumuri.
stud. Cosmin-Dumitru Oprea
UPB, Facultatea de Automatică şi Calculatoare Bucureşti