Расстояние между вершинами в дереве. [Решено]

Revision ru2, by Wsl_F, 2016-01-21 16:10:44

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). На этом все((

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

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

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
ru2 Russian Wsl_F 2016-01-21 16:10:44 39 Мелкая правка: 'Всем приве' -> '**UPD:** Уже решено.\n\nВсем приве'
ru1 Russian Wsl_F 2016-01-21 15:15:42 1030 Первая редакция (опубликовано)