== include(page="template/taskheader" task_id="arborigami") ==
Poveste şi cerinţă...
!>problema/arborigami?unknown.png!
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 $a{~i~}$ şi $b{~i~}$ existente în acel moment în arbore.
* Notează cu $V$ mulţimea vecinilor nodurilor $a{~i~}$ şi $b{~i~}$ (nodurile care au o muchie directă către cel puţin unul dintre $a{~i~}$ sau $b{~i~}$).
* Şterge din $V$ nodurile $a{~i~}$ şi $b{~i~}$, dacă acestea erau prezente.
* Şterge din arbore nodurile $a{~i~}$ şi $b{~i~}$, cât şi muchiile care aveau cel puţin un capăt într-unul din nodurile $a{~i~}$ şi $b{~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.
h2. Date de intrare
Fişierul de intrare $arborigami.in$ ...
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 $u{~i~}$ şi $v{~i~}$, reprezentând nodurile unite de a $i$-a muchie din arbore.
h2. Date de ieşire
În fişierul de ieşire $arborigami.out$ ...
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 $a{~i~}$ şi $b{~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.
h2. 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.
|_. # |_. Punctaj |_. Restricţii |
| $1$
$2$
$3$
$4$
| $10$
$20$
$10$
$60$
| $1 ≤ N ≤ 15$
$1 ≤ N ≤ 200$
$u{~i~} = i, v{~i~} = i + 1$ pentru $1 ≤ i < N$.
Nu există alte restricţii.
|
h2. Exemplu
table(example). |_. arborigami.in |_. arborigami.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicaţie
...
table(example). |_. arborigami.in |_. arborigami.out |_. Explicaţii |
| 5
1 2
2 3
3 4
4 5
| 1
2 4
| Se efectuează o singură operaţie de împăturire, între nodurile 2 şi 4. Operaţia decurge în felul următor:
- vecinii nodurilor 2 şi 4 sunt V = 1, 3, 5
- ştergem nodurile 2 şi 4 din arbore
- adăugăm nodul N + 1 = 6 şi muchiile (1, 6), (3, 6), (5, 6)
Arborele final este cel compus din nodurile 1, 3, 5 şi 6 şi muchiile (1, 6), (3, 6), (5, 6).
Observăm că nodurile 1, 3 şi 5 au un singur vecin şi doar 6 are 3 vecini, deci arborele rezultat este stea.
|
| 6
1 2
2 3
3 4
4 5
5 6
| 2
2 4
5 7
| Se efectuează două operaţii de împăturire:
- (2, 4), adăugând nodul N + 1 = 7;
- (5, 7), adăugând nodul N + 2 = 8.
Arborele final este cel compus din nodurile 1, 3, 6 şi 8 şi muchiile (1, 8), (3, 8), (6, 8).
|
== include(page="template/taskfooter" task_id="arborigami") ==
