Level Ancestor problem

Материал из Викиконспекты
Перейти к: навигация, поиск

Задача о уровне предка - (англ. "Level Ancestor problem") является задачей о превращении данного корневого дерева T в структуру данных, которая сможет определить предка любого узла на заданном расстоянии от корня дерева.

Задача:
Дано корневое дерево [math]T[/math] c [math]n[/math] вершинами. Поступают запросы вида [math](v, k)[/math], для каждого из которых необходимо найти предка вершины [math]v[/math], который находится на расстоянии [math]k[/math] от корня дерева [math]T[/math].