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

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