In Hackerville există un parc special. Acest parc are N copaci uniţi prin N-1 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 copaci.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 k_i 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 copaci.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 k_i copaci din interogarea i.

Restricţii

• 1<= N, M<= 100 000
• 1<= k <= N
• Pentru 40% din teste 1 <= N <= 1 000

Exemple

copaci.in	copaci.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

opreacosmind@gmail.com