== include(page="template/taskheader" task_id="lca") ==
Se dă un "arbore":https://en.wikipedia.org/wiki/Tree_%28graph_theory%29 cu rădăcină T. "Cel mai apropiat strămoș comun": https://en.wikipedia.org/wiki/Lowest_common_ancestor a două noduri u și v este nodul w care este strămoș al ambelor noduri u și v și are cea mai mare adâncime în T.
Se dă un "arbore":https://en.wikipedia.org/wiki/Tree_%28graph_theory%29 cu rădăcină [$T$]. "Cel mai apropiat strămoș comun":https://en.wikipedia.org/wiki/Lowest_common_ancestor a două noduri $u$ și $v$ este nodul $w$ care este strămoș al ambelor noduri $u$ și $v$ și are cea mai mare adâncime în [$T$].
Considerăm că arborele T are n noduri și are rădăcina în nodul 1. Dându-se o mulțime arbitrară P = {{u,v}}, cu m perechi neordonate de noduri din T, se cere să se determine cel mai apropiat strămoș al fiecărei perechi din P.
Considerăm că arborele $T$ are $n$ noduri și are rădăcina în nodul [$1$]. Dându-se o mulțime arbitrară $P = {{u,v}}$, cu $m$ perechi neordonate de noduri din [$T$], se cere să se determine cel mai apropiat strămoș al fiecărei perechi din [$P$].
h2. Date de intrare
Fișierul de intrare $lca.in$ ...
Pe prima linie a fișierului de intrare $lca.in$ se găsesc $n$ și [$m$]. Următoarea linie conține $n-1$ numere naturale, cel de-al [$i$]-lea număr reprezentând tatăl nodului $i+1$ (nodul $1$ fiind rădăcină nu are tată). Pe următoarele $m$ linii se află câte o pereche de numere naturale, reprezentând elementele mulțimii [$P$].
h2. Date de ieșire
În fișierul de ieșire $lca.out$ ...
Fișierul de ieșire $lca.out$ va conține $m$ linii, linia a [$i$]-a conținând răspunsul celei de a [$i$]-a întrebări.
h2. Restricții
* $... ≤ ... ≤ ...$
* $1 ≤ n ≤ 100 000$
* $1 ≤ m ≤ 2 000 000$
h2. Exemplu
table(example).
|_. lca.in |_. lca.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 11 5
1 1 2 2 2 4 4 6 3 3
10 11
8 9
5 11
5 6
4 2
| 3
2
1
2
2
|
h3. Explicație
...
== include(page="template/taskfooter" task_id="lca") ==
