parb2

Parb2

== include(page="template/taskheader" task_id="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.

 
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$.

h2. 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.

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.

h2. 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.

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$.

h2. 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.

* $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$.

h2. Exemplu