Fişierul intrare/ieşire:parb2.in, parb2.outSursăLot Măgurele 2016 - Baraj 4 Seniori
AutorEugenie Daniel PosdarascuAdăugată deatatomirTatomir Alex atatomir
Timp execuţie pe test5 secLimită de memorie262144 kbytes
Scorul tăuN/ADificultateN/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.inparb2.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
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?