Farmer John voit que ses vaches passent souvent entre champs voisins. Il veut donc planter assez d’herbe dans chaque champ pour les vaches locales et celles qui viennent des environs.

La ferme comporte $N$ champs ($1 \le N \le 100{,}000$), certains reliés par des sentiers bidirectionnels, $N-1$ au total. Entre deux champs $i$, $j$, le chemin est unique. Le champ $i$ abrite $C(i)$ vaches, qui peuvent parfois traverser jusqu’à $K$ sentiers ($1 \le K \le 20$).

Le champ $i$ doit nourrir le maximum $M(i)$ de vaches pouvant y arriver, soit celles atteignant le champ par au plus $K$ sentiers. Avec la structure et chaque $C(i)$, calculez tous les $M(i)$.

Entrée

• Ligne $1$ : entiers $N$, $K$ séparés par un espace.

• Lignes $2\ldots N$ : entiers $i$, $j$ séparés par un espace ($1 \le i,j \le N$), champs reliés directement.

• Lignes $N+1\ldots2N$ : la ligne $N+i$ donne l’entier $C(i)$ ($0 \le C(i) \le 1000$).

Sortie

• Lignes $1\ldots N$ : la ligne $i$ donne $M(i)$.

Exemples

Entrée 1

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

Sortie 1

15
21
16
10
8
11

Remarque

Il y a $6$ champs, avec sentiers $(5,1)$, $(3,6)$, $(2,4)$, $(2,1)$, $(3,2)$. Le champ $i$ a $C(i)=i$ vaches.

Le champ $1$ a $M(1)=15$ vaches à distance d’au plus $2$ sentiers, etc.

Auteurs du problème : Neal Wu et Eric Price, 2011