Revizia anterioară Revizia următoare
Fişierul intrare/ieşire: | dedicatie.in, dedicatie.out | Sursă | Concursul National de Informatica "Adolescent Grigore Moisil" 18 |
Autor | Chichirim George | Adăugată de | AGMInformatica •AGMinformatica |
Timp execuţie pe test | 0.6 sec | Limită de memorie | 262144 kbytes |
Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Dedicatie
Cu totii stim ca dedcatiile 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 .
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:
- 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
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
Exemplu
dedicatie.in | dedicatie.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
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