Level Ancestor problem — различия между версиями
Romech (обсуждение | вклад) (Новая страница: «'''Задача о уровне предка''' - (англ. "Level Ancestor problem") является задачей о превращении данного к…») |
Romech (обсуждение | вклад) |
||
| Строка 1: | Строка 1: | ||
| − | '''Задача о уровне предка''' - (англ. "Level Ancestor problem") является задачей о превращении данного корневого дерева T в структуру данных, которая сможет определить предка | + | '''Задача о уровне предка''' - (англ. "Level Ancestor problem") является задачей о превращении данного корневого дерева T в структуру данных, которая сможет определить предка любого узла на заданном расстоянии от корня дерева. |
| + | {{Задача | ||
| + | |definition = Дано корневое дерево <tex>T</tex> c <tex>n</tex> вершинами. Поступают запросы вида <tex>(v, k)</tex>, для каждого из которых необходимо найти предка вершины <tex>v</tex>, который находится на расстоянии <tex>k</tex> от корня дерева <tex>T</tex>. | ||
| + | }} | ||
Версия 18:35, 6 мая 2019
Задача о уровне предка - (англ. "Level Ancestor problem") является задачей о превращении данного корневого дерева T в структуру данных, которая сможет определить предка любого узла на заданном расстоянии от корня дерева.
| Задача: |
| Дано корневое дерево c вершинами. Поступают запросы вида , для каждого из которых необходимо найти предка вершины , который находится на расстоянии от корня дерева . |
