Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | parb2.in, parb2.out | Sursă | Lot Măgurele 2016 - Baraj 4 Seniori |
| Autor | Eugenie Daniel Posdarascu | Adăugată de |  Tatomir Alex •atatomir |
| Timp execuţie pe test | 2.5 sec | Limită de memorie | 262144 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Parb2
Avem un arbore cu N noduri şi rădăcina în nodul 1, indexat de la 1 la N. Fiecare muchie este etichetată cu o literă.
Pentru două noduri (x, y) unde x este strămoş al lui y definim şirul strămoşesc ca fiind concatenarea muchiilor drumului de la y la x.
Pe acest arbore se fac Q întrebări, o întrebare are forma unei perechi (x,y) unde x este un strămoş de-al lui y. Fie S şirul strămoşesc corespunzător nodurilor x şi y.
Pentru fiecare întrebare trebuie să găsiţi câte perechi (a,b) (inclusiv (x,y) ) dau şirul strămoşesc egal cu S.
Date de intrare
Fişierul de intrare parb2.in conţine pe prima linie numărul N de noduri, urmat de numărul Q de întrebări. Vor urma N–1 linii, fiecare linie va conţine un triplet (x, y, c) reprezentând că există o muchie de la x la y care este etichetată cu caracterul c. Urmează Q linii, pe fiecare linie se află câte o pereche (x, y) corespunzătoare unei întrebări.
Date de ieşire
Fişierul de ieşire parb2.out va conţine Q linii. Pe linia i se va afla un singur întreg, răspunsul la întrebarea i.
Restricţii
- 1 ≤ N ≤ 100 000
- 0 ≤ Q ≤ 100 000
- Muchiile sunt etichetate cu litere mici ale alfabetului englez ( 'a' .. 'z' ).
- Pentru teste în valoare de 20 puncte, N ≤ 100.
Exemplu
| parb2.in | parb2.out |
|---|---|
| 10 4 1 2 m 2 3 m 3 4 c 3 5 c 5 6 l 2 7 c 1 8 c 8 9 m 9 10 c 2 5 1 9 9 10 1 4 | 4 1 5 2 |
