Insula CLand este formată din N aşezări obşteşti, numerotate de la 1 la N, legate între ele prin N-1 poteci bidirecţionale. Se ştie că există o singură modalitate de a ajunge de la oricare aşezare la oricare alta folosind doar potecile existente (cu alte cuvinte, insula are forma unui arbore).
Fiecare aşezare are un coeficient de inteligenţă al persoanelor ce locuiesc acolo (număr întreg, posibil negativ).
Comisia de cenzură vrea să împartă insula în K judeţe astfel încât între oricare două aşezări din acelaşi judeţ să se poată ajunge de la una la cealaltă folosind potecile existente şi fără a părăsi vreodată judeţul.
Numim anarhia unui judeţ diferenţa dintre coeficientul maxim şi cel minim de inteligenţă al aşezărilor din judeţ. Numim anarhia totală suma anarhiilor celor K judeţe.
Cerință
Dându-se valoarea lui N, cele N-1 poteci din CLand şi valorile coeficienţilor de inteligenţă ale celor N aşezări, se cere pentru fiecare valoare K de la 1 la N anarhia maximă posibilă a unei împărţiri în fix K judeţe ale insulei.
Date de intrare
Pe prima linie a fişierului de intrare anarhie.in se află valoarea N, reprezentând numărul de aşezări din CLand. Pe a doua linie se află N numere întregi separate prin spaţii, reprezentând coeficienţii de inteligenţă asociaţi celor N aşezări. Următoarele N-1 linii vor conţine câte două numere a şi b, separate printr-un spaţiu, semnificând că există o potecă între aşezările a şi b.
Date de ieșire
Pe prima linie a fişierului de ieşire anarhie.out se află N numere, separate prin spaţii, al K-lea dintre ele reprezentând anarhia maximă posibilă a unei împărţiri în K judeţe ale insulei.
Restricții
1 ≤ N ≤ 2 000-1 000 000 ≤ coeficienţii de inteligenţă ≤ 1 000 000- Pentru teste în valoare de
12puncteN ≤ 20 - Pentru alte teste în valoare de
63puncteN ≤ 300
Exemple
anarhie.in
5
5 6 7 -7 3
3 5
1 5
2 1
4 1
anarhie.out
14 17 16 12 0
anarhie.in
17
1 3 -2 9 4 -2 5 -9 3 -8 -3 6 9 5 -2 -7 -5
14 1
13 14
14 6
6 8
12 2
3 1
11 4
3 10
1 5
6 7
2 9
16 5
12 10
17 15
4 10
17 7
anarhie.out
18 35 47 56 65 68 68 68 68 65 61 54 47 38 28 17 0