| Fişierul intrare/ieşire: | color2.in, color2.out | Sursă | ONI 2004 |
| Autor | Mugurel Ionut Andreica | Adăugată de | |
| Timp execuţie pe test | 0.05 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate |   3/5 |
Vezi solutiile trimise | Statistici
Color2
Ion si Vasile joaca un joc. Ei au la dispozitie un arbore binar strict (adica fiecare nod are 0 sau 2 fii) cu N noduri, numerotate de la 1 la N (nodul numerotat cu 1 este radacina arborelui). Initial, toate nodurile sunt colorate in alb. Jucatorii vor efectua mutari alternativ, iar jucatorul aflat la mutare va colora in negru un nod colorat in alb. Ion efectueaza prima mutare si poate colora in negru orice nod al arborelui. Considerand ca ultimul nod colorat de unul dintre jucatori este P, jucatorul care urmeaza la mutare poate colora in negru unul din urmatoarele noduri (daca nu au fost deja colorate in negru):
- unul din cei doi fii ai lui P (daca P nu este frunza in arbore)
- tatal lui P (daca P nu este radacina arborelui)
Jocul continua pana cand unul dintre jucatori nu mai poate efectua nici o mutare. Atunci, jucatorul care a efectuat ultima mutare este considerat castigator.
Cerinta
Considerand ca ambii jucatori joaca optim, determinati toate nodurile din arbore pe care le poate colora Ion la prima mutare, astfel incat sa fie sigur de victorie.
Date de Intrare
Prima linie a fisierului color2.in contine numarul intreg N, reprezentand numarul de noduri din arbore. Urmatoarele N-1 linii contin cate doua numere intregi separate printr-un spatiu, a si b, avand semnificatia ca a este tatal lui b.
Date de Iesire
Pe prima linie a fisierului color2.out veti afisa numarul intreg M, reprezentand numarul de noduri pe care le poate colora Ion la prima mutare, astfel incat sa fie sigur de victorie. Pe urmatoarea linie veti afisa numerele acestor noduri, in ordine crescatoare.
Restrictii si precizari
- 1 ≤ N ≤ 16 000, N impar
Exemplu
| color2.in | color2.out |
|---|---|
| 9 1 2 1 3 2 4 2 5 4 6 4 7 3 8 3 9 | 6 1 5 6 7 8 9 |
