Fișierul intrare/ieșire	lca.in, lca.out	Sursă	Infoarena
Autor	teorie	Adăugată de	Tudor Coman • tudorcoman
Timp de execuție pe test	0.9 sec	Limită de memorie	65536 KB
Scorul tău	N/A	Dificultate	N/A

Vezi soluțiile trimise | Statistici

Lowest Common Ancestor

Se dă un arbore 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.

Date de intrare

Fișierul de intrare lca.in ...

Date de ieșire

În fișierul de ieșire lca.out ...

Restricții

• ... ≤ ... ≤ ...

Exemplu

Explicație

...