UPD: Уже решено.
Всем привет! Встретилась задача и я не догадываюсь как ее решать((
Условие:
Есть взвешенное дерево из N (N <= 150 000) вершин Q (Q <= 75 000) запросов: найти кратчайшее расстояние между парой вершин.
Мои скудные соображения: 1. Традиционный поиск в ширину/глубину дает сложность O( N*Q ) — слишком много. 2. Алгоритм Флойда-Уоршелла дает O ( N^3 + Q) — еще хуже. 3. Мне кажеться, что должен быть какой-то препроцессинг за O(N * logN) или O(N^1.5) и выполнение запросов за O(log N) или O(N^0.5). На этом все((
Задача не с олимпиады или соревнования, нам показали пример вступительных билетов в магистратуру. Фото (на украинском) ниже:
1) Подвесим за какую — нибудь вершину.
2) Пусть way[i] = расстояние от корня до вершины номер i
3) пришел запрос (u, v) :
пусть z = lca(u, v), тогда кратчайшее расстояние от u до v есть
S = (way[u] — way[z])[расстояние от u до z] + (way[v] — way[z])[расстояние от v до z]
Большое спасибо! действительно все так просто))