Revizia anterioară Revizia următoare
Fişierul intrare/ieşire: | arborigami.in, arborigami.out | Sursă | ONI 2022 Baraj Seniori Ziua 2 |
Autor | Vlad Gavrila | Adăugată de | Lorintz Alexandru •Alex_tz307 |
Timp execuţie pe test | 1 sec | Limită de memorie | 262144 kbytes |
Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Miyuki vrea să împăturească arborigami
Kaguya, vicepreşedintele consiliului de studenţi, este răcită. Miyuki vrea, cum este tradiţional, să îi ofere cadou o mie de cocori de hârtie. Poate nu o mie... (prea exagerat pentru o simplă răceală), şi poate nu cocor... (prea tradiţional şi oricum nu am hârtie de origami...). Un arbore stea ar trebui să fie ideal!
Miyuki are un arbore (graf conex aciclic) format din N noduri numerotate de la 1 la N. El doreşte să îl transforme într-un arbore stea de dimensiune N − K, adică un graf conex aciclic care are cel puţin N − K − 1 frunze (noduri cu exact 1 vecin).
Pentru a transforma arborele său într-un arbore stea, Miyuki va efectua K operaţii de împăturire a câte două noduri. Pentru a i-a operaţie de împăturire, Miyuki:
- Alege două noduri distincte şi existente în acel moment în arbore.
- Notează cu V mulţimea vecinilor nodurilor şi (nodurile care au o muchie directă către cel puţin unul dintre sau ).
- Şterge din V nodurile şi , dacă acestea erau prezente.
- Şterge din arbore nodurile şi , cât şi muchiile care aveau cel puţin un capăt într-unul din nodurile şi .
- Adaugă în arbore un nod cu numărul N + i.
- Adaugă muchii între nodul N + i şi fiecare din nodurile din mulţimea V.
După o astfel de operaţie, graful rezultat trebuie să fie în continuare arbore; mai precis, operaţia efectuată nu trebuie să introducă vreun ciclu. Altfel, operaţia este invalidă şi nu poate fi efectuată.
Deoarece nu vrea să pară că s-a străduit prea mult, Miyuki vrea să facă un număr K minim de operaţii. Pentru că secretara Chika a promis că nu îl mai învaţă nimic, trebuie să-l ajutaţi pe Miyuki să determine:
1. Care este numărul minim K de operaţii pentru a transforma arborele iniţial în arbore stea.
2. Care sunt cele K operaţii prin care arborele iniţial este transformat într-un arbore stea.
Date de intrare
De pe prima linie se va citi un singur număr natural N, reprezentând dimensiunea arborelui iniţial. Pe următoarele N − 1 linii vor fi descrise muchiile arborelui iniţial, pe linia i + 1 aflându-se două numere naturale şi , reprezentând nodurile unite de a i-a muchie din arbore.
Date de ieşire
Pe prima linie se va afişa un singur număr natural K, reprezentând numărul minim de operaţii ce trebuie efectuate. Pe următoarele K linii se vor afişa K perechi de numere naturale şi (1 ≤ i ≤ K), separate prin câte un spaţiu, reprezentând, în ordine, operaţiile de împăturire ce se efectuează asupra arborelui.
Restricţii
- 1 ≤ N ≤ 500 000
- Dacă există mai multe soluţii posibile, se poate afişa oricare.
- Dacă se determină corect numărul minim de operaţii K, dar operaţiile afişate nu transformă corect arborele într-unul stea, sau una dintre operaţii este invalidă conform cu definiţia din enunţ, se va acorda 30% din punctaj.
Exemplu
arborigami.in | arborigami.out |
---|---|
5 1 2 2 3 3 4 4 5 | 1 2 4 |
Explicaţie
...