Fişierul intrare/ieşire:acolor.in, acolor.outSursăBaraj 2006
AutorEmilian MironAdăugată de
Timp execuţie pe test0.125 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

Acolor

Omida-agent Smith s-a saturat sa tot distruga arborii si acum isi dezvolta simtul artistic - ii place mult mai mult sa-i coloreze.
De fiecare data cand vrea sa creeze o noua arbo-pictura isi ia cu el cele K creioane colorate, isi alege un arbore din gradina si porneste la lucru.
Arborele ales de Smith este alcatuit din N noduri, are ca radacina nodul R si o forma potrivita pentru pictura:

  • fiecare nod are cel mult doua crengi care duc spre doua noduri: unul la stanga si/sau unul la dreapta;
  • intre oricare doua noduri exista un drum unic format din crengi distincte, pe care omida se poate plimba pentru a ajunge de la un nod la celalalt;
  • nodurile din subarborele stang al unui nod sunt toate plasate mai la stanga decat acesta, iar cele din subarborele drept sunt toate mai la dreapta, de aceea nodurile au fost etichetate de la 1 la N de la cel mai din stanga pana la cel mai din dreapta.

Omida a observat ca picturile sale sunt frumoase doar daca respecta unele reguli de baza pe care le-a citit intr-o carte:

  • orice nod trebuie sa fie colorat cu exact una dintre cele K culori;
  • un nod trebuie sa fie colorat diferit fata de parintele dinspre radacina (adica fata de nodul care preceda nodul respectiv atunci cand omida se plimba pe drumul de la radacina la nod);
  • privit din exterior arborele trebuie sa fie colorat diferit de la stanga la dreapta: orice nod are o culoare diferita de cel mai apropiat nod la stanga de el si fata de cel mai apropiat nod la dreapta (cu alte cuvinte culoarea nodului etichetat cu i trebuie sa fie diferita de culoarea nodurilor etichetate cu i-1, i+1).

Cerinta

Scrieti un program care sa determine pentru un arbore dat in cate picturi frumoase (picturi care sa respecte criteriile din enunt) poate fi transformat acesta. Deoarece numarul cerut poate fi foarte mare, este suficient sa aflati restul impartirii la 10007.

Date de Intrare

Fisierul de intrare acolor.in va contine pe prima linie numerele intregi N, R, K separate prin cate un spatiu. Pe urmatoarele N linii este descrisa structura arborelui. Mai exact, pe linia i+1 vor exista doua numere sti, dri separate printr-un spatiu, reprezentand nodul fiu spre stanga si respectiv nodul fiu spre dreapta al nodului i. Daca un nod nu are fiu spre stanga si/sau fiu spre dreapta atunci numarul corespunzator va fi 0.

Date de Iesire

Fisierul de iesire acolor.out va contine o singura linie pe care va fi scris numarul de picturi frumoase care se pot obtine pentru arborele dat.

Restrictii si precizari

  • 0 < N ≤ 100 000, 1 ≤ R ≤ N, 1 ≤ K ≤ 100
  • In 40% din teste sunt indeplinite relatiile N ≤ 100 si K ≤ 10
  • In 60% din teste sunt indeplinite relatiile N ≤ 400 si K ≤ 15

Exemple

acolor.inacolor.outfigura
9 5 4
0 0
1 3
0 4
0 0
2 6
0 7
0 9
0 0
8 0
3601
3 1 2
0 3
0 0
2 0
0
 
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content