== include(page="template/taskheader" task_id="anarhie") ==
Poveste şi cerinţă...
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.
h2. 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.
h2. Date de intrare
Fişierul de intrare $anarhie.in$ ...
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$.
h2. Date de ieşire
În fişierul de ieşire $anarhie.out$ ...
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.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ N ≤ 2.000$
* $-1.000.000 ≤ coeficienţii de inteligenţă ≤ 1.000.000$
* Pentru teste în valoare de 12 puncte $N ≤ 20$
* Pentru teste în valoare de 63 puncte $N ≤ 300$
h2. Exemplu
table(example). |_. anarhie.in |_. anarhie.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicaţie
...
| 5
5 6 7 -7 3
3 5
1 5
2 1
4 1
| 14 17 16 12 0
|
| 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
| 18 35 47 56 65 68 68 68 68 65 61 54 47 38 28 17 0
|
== include(page="template/taskfooter" task_id="anarhie") ==
