Тема: Дерево.
Как можно отвечать на запрос длины минимального пути в дереве из вершини А к вершине В? Сложность ответа не более Log N.
Спасибо.
P.S. Само N <= 100000;
1 2010-02-11 21:31:37 Отредактировано witua (2010-02-11 21:42:09)
Re: Дерево.
Найти наименьшего общего предка - см. LCA. А дальше задача сводится к длине пути от одной вершины до какого-то её предка,и это уже гораздо более простая задача. Проще всего считать эту длину на ходу,по ходу нахождения наименьшего нашего предка, для чего удобно применить алгоритм двоичного подъема, описанный на этом сайте.
3 2010-02-11 22:40:33 Отредактировано KADR (2010-02-11 22:41:02)
Re: Дерево.
Выделим какую-то вершину root как корень. Посчитаем расстояние от корня до всех остальных вершин.
Тогда, если поступает запрос нахождения кратчайшего пути между A и B, то пусть C - их наименьший общий предок. Легко показать, что dist(A,B)=dist(root,A)+dist(root,B)-2*dist(root,C). На этом сайте описано, как быстро находить LCA. Если использовать эффективный алгоритм, то тут можно получить сложность даже O(N+M), где N - кол-во вершин, а M - кол-во запросов.
Edit: пока писал, уже ответили.