infoarena informatica de performanta

Bad macro "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. 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. 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. 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. h2. Exemplu table(example). |_. 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 | == include(page="template/taskfooter" task_id="parb2")"