Fişierul intrare/ieşire:dedicatie.in, dedicatie.outSursăConcursul National de Informatica "Adolescent Grigore Moisil" 18
AutorChichirim GeorgeAdăugată deAGMinformaticaAGMInformatica AGMinformatica
Timp execuţie pe test0.6 secLimită de memorie262144 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Dedicatie

Cu totii stim ca dedicatiile la o petrecere sunt foarte scumpe. Marele artist Sorin Pastrama v-a propus un targ: daca il ajutati la rezolvarea urmatoarei probleme el va va face cate decicatii doriti la urmatoarea petrecere, PE GRATIS. Problema suna cam asa:

Se da un arbore cu N noduri. Se garanteaza ca oricum ai alege un nod pe care sa il elimini din arbore, atunci exista cel putin un subarbore din cei rezultati care are marimea  \geq \left\lfloor\frac{N+1}{2}\right\rfloor .
Fie vali egal cu valoarea muchiei i. Initial vali = 0 ( 1 ≤ i ≤ N-1 ). Vom lua fiecare pereche de noduri 1 ≤ x < y ≤ N si vom incrementa cu 1 valoarea fiecarei muchii de pe drumul de la x la y. Vom sorta muchiile descrescator dupa valoarea acestora (iar in caz de egalitate, crescator dupa indicele muchiei) si le vom normaliza. Adica prima muchie din sortare va avea valoarea egala cu 0, a doua muchie va avea valoarea egala cu 1, ..., ultima muchie din sortare va avea valoarea egala cu N-2. Acum, valoarea finala a muchiei i va fi egala cu ( vali * alfa[vali] ) % 100003, unde alfa este un vector de lungime N-1 dat in input.
Se cere sa se afiseze o permutare p(1), p(2), ..., p(N) a numerelor de la 1 la N care satisface urmatoarele proprietati:

  •  \sum_{i=1}^{N} dist(i, p(i)) este maxima, unde dist(i, j) = lungimea lantului elementar dintre nodurile i si j
  • Sirul de perechi { (p(1) -> 1, p(1)) , (p(2) -> 2, p(2)) , ... , (p(N) -> N, p(N)) } este minim lexicografic, unde p(i) -> i reprezinta sirul valorilor finale muchiilor de pe drumul de la nodul p(i) la nodul i, in oridnea in care ele apar pe drum

Date de intrare

Fişierul de intrare dedicatie.in contine pe prima linie numarul natural N, cu semnificatia din enunt. Pe urmatoarele N-1 linii se afla cate doua numere naturale x si y cu semnificatia ca exista o muchie intre aceste doua noduri. Pe ultima linie a fisierului de intrare se afla cele N-1 elemente ale vectorului alfa separate prin cate un spatiu (vectorul este indexat de la 0).

Date de ieşire

În fişierul de ieşire dedicatie.out se vor afla N linii, pe a i-a aflandu-se valoarea lui p(i).

Restricţii

  • 1 ≤ N ≤ 105
  • 1 ≤ alfa[i] < 100003, 0 ≤ i ≤ N-2
  • O pereche (a, b) este mai mica ca o pereche (x, y) daca a < x sau daca a = x si b < y
  • Un sir { a1, a2, ..., ak } este mai mic lexicografic ca sirul { b1, b2, ..., bs } daca exista o pozitie 1 ≤ i ≤ min(k, s) astfel incat a1 = b1, a2 = b2, ..., ai-1 = bi-1 si ai < bi sau daca a1 = b1, a2 = b2, ..., ak = bk si k < s
  • Replica preferata a lui Sorin Pastrama este: "Ai gresit buzunarul baiatul meu!"

Exemplu

dedicatie.indedicatie.out
6
5 4
4 2
3 1
4 6
1 5
7574 2 1 66670 25002
4
5
2
1
6
3

Explicaţie

Dupa ce parcurgem fiecare drum si incrementam cu 1 muchiile, valorile acestora sunt:
muchia 1 (5 -> 4): 9
muchia 2 (4 -> 2): 5
muchia 3 (3 -> 1): 5
muchia 4 (4 -> 6): 5
muchia 5 (1 -> 5): 8

Dupa normalizare, muchiile au valorile:
muchia 1 (5 -> 4): 0
muchia 2 (4 -> 2): 2
muchia 3 (3 -> 1): 3
muchia 4 (4 -> 6): 4
muchia 5 (1 -> 5): 1

Dupa inmultirea cu alfa, muchiile au valorile finale:
muchia 1 (5 -> 4): (0 * 7574) % 100003 = 0
muchia 2 (4 -> 2): (2 * 1) % 100003 = 2
muchia 3 (3 -> 1): (3 * 66670) % 100003 = 4
muchia 4 (4 -> 6): (4 * 25002) % 100003 = 5
muchia 5 (1 -> 5): (1 * 2) % 100003 = 2

Permutarea optima este: 4 5 2 1 6 3
 \sum_{i=1}^{6} dist(i, p(i)) = 2 + 2 + 4 + 2 + 2 + 4 = 16 si este maxima
Sirul de perechi este: { ({0, 2}, 4) , ({0, 2}, 5) , ({2, 0, 2, 4}, 2) , ({2, 0}, 1) , ({5, 0}, 6) , ({4, 2, 0, 5}, 3) } si este minim lexicografic

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?