Fişierul intrare/ieşire:portocal.in, portocal.outSursăONI 2022 Baraj Seniori Ziua 1
AutorAlexandra UdristoiuAdăugată decadmium_Voicu Mihai Valeriu cadmium_
Timp execuţie pe test1.25 secLimită de memorie262144 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Portocal

Ana a primit un arbore cu N noduri cu rădăcina în nodul 1, unde fiecare nod are asociată o valoare naturală de la 1 la M. Pentru fiecare nod, va scrie câte un şir format din valorile nodurilor de pe lanţul de la rădăcină la acel nod, în ordine. Apoi, va sorta cele N şiruri lexicografic.

După ce a obţinut şirurile sortate, Ana se gândeşte la un şir S format din K numere naturale cuprinse, de asemenea, între 1 şi M, şi îl întreabă pe Portocal dacă există cel puţin un şir egal cu S. Cum Portocal este un motan leneş, el va verifica în fiecare zi un singur şir, începând cu primul în ordinea sortării, până când va găsi unul egal cu S.

Portocal a observat că unele noduri din arbore nu au încă asociată o valoare, aşa că şi-a propus să dea el valori acestor noduri (tot între 1 şi M) înainte ca Ana să se apuce de scris şirurile. Scopul lui este să găsească şirul S cât mai repede. Pentru a decide cum să completeze valorile din arbore, are nevoie de răspunsul la două întrebări:

  1. Numărul minim de zile în care Portocal poate găsi şirul S
  2. Numărul de moduri în care poate completa valorile lipsă din arbore astfel încât să obţină acel număr minim de zile. Cum acest număr poate fi foarte mare, se mulţumeşte cu restul împărţirii la 1 000 000 009 (109 + 9)

Evident, Portocal îşi doreşte să găsească cel puţin un şir egal cu S. Se garantează că există cel puţin o modalitate de a completa valorile arborelui pentru a realiza acest lucru.

Date de intrare

Pe prima linie a fişierul de intrare portocal.in se va afla un număr C. Dacă C = 1, trebuie răspuns la întrebarea 1, iar dacă C = 2, trebuie răspuns la întrebarea 2. Pe a doua linie se vor afla numerele N, M şi K. Pe a treia linie se găsesc N numere naturale val1,...,valN , reprezentând valorile asociate nodurilor din arbore. Dacă vali este −1, înseamnă că nodul i nu are încă asociată o valoare. Pe a patra linie se vor afla K numere naturale reprezentând şirul S. Următoarele N − 1 linii vor conţine câte două numere u şi v, reprezentând muchiile arborelui.

Date de ieşire

În fişierul de ieşire portocal.out se va afişa un singur număr reprezentând răspunsul la prima, respectiv a doua întrebare, în funcţie de valoarea lui C.

Restricţii

  • C ∈ {1, 2}
  • 1 ≤ K ≤ N ≤ 500 000
  • 1 ≤ M ≤ 500 000
  • 1 ≤ vali ≤ M sau vali=−1, pentru oricare 1 ≤ i ≤ N
  • 1 ≤ Si ≤ M, pentru oricare 1 ≤ i ≤ K

Subtaskuri

#PunctajRestricţii
18C = 1, N ≤ 13, M ≤ 3
219C = 1, N ≤ 5 000
322C = 1
411C = 2, N ≤ 13, M ≤ 3
640C = 2

Exemple

portocal.inportocal.out
1
8 3 3
-1 -1 2 -1 -1 -1 1 2
1 2 2
1 2
2 3
2 4
4 5
1 6
6 7
1 8
4
2
8 3 3
-1 -1 2 -1 -1 -1 1 2
1 2 2
1 2
2 3
2 4
4 5
1 6
6 7
1 8
6

Explicaţii

Pentru primul exemplu:

Portocal poate completa valorile nodurilor astfel: 1 2 2 2 1 3 1 2.
Primele şiruri în ordine lexicografică vor fi:
1 - pentru nodul 1
1 2 - pentru nodul 2
1 2 - pentru nodul 8
1 2 2 - pentru nodul 3, care este egal cu S.
Astfel, răspunsul este 4.
Observaţi că, deşi mai există un şir egal cu S, pentru nodul 4, Portocal se opreşte când îl va găsi pe primul.

Pentru cel de-al doilea exemplu:

Există 6 moduri de a completa valorile din arbore astfel încât Portocal să găsească şirul S în ziua 4. Acestea sunt:
1 2 2 2 1 3 1 2
1 2 2 3 1 3 1 2
1 2 2 2 2 3 1 2
1 2 2 3 2 3 1 2
1 2 2 2 3 3 1 2
1 2 2 3 3 3 1 2

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?