| Fişierul intrare/ieşire: | anarhie.in, anarhie.out | Sursă | ONI 2019, baraj |
| Autor | Andrei Constantinescu | Adăugată de |  Tinca Matei •TincaMatei |
| Timp execuţie pe test | 0.3 sec | Limită de memorie | 524288 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Anarhie
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 12 puncte N ≤ 20
- Pentru teste în valoare de 63 puncte N ≤ 300
Exemplu
| anarhie.in | anarhie.out |
|---|---|
| 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 |
