Расстояние между вершинами в дереве. Нужна помощ

Правка ru1, от WasylF, 2016-01-21 15:15:42

Всем привет! Встретилась задача и я не догадываюсь как ее решать((

Условие:

Есть взвешенное дерево из 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). На этом все((

Задача не с олимпиады или соревнования, нам показали пример вступительных билетов в магистратуру. Фото (на украинском) ниже:

Теги граф, дерево, нужна помощь, кну

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
ru2 Русский WasylF 2016-01-21 16:10:44 39 Мелкая правка: 'Всем приве' -> '**UPD:** Уже решено.\n\nВсем приве'
ru1 Русский WasylF 2016-01-21 15:15:42 1030 Первая редакция (опубликовано)