Fişierul intrare/ieşire:anarhie.in, anarhie.outSursăONI 2019, baraj
AutorAndrei ConstantinescuAdăugată deTincaMateiTinca Matei TincaMatei
Timp execuţie pe test0.6 secLimită de memorie524288 kbytes
Scorul tăuN/ADificultateN/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.inanarhie.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
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?