Решение этой задачи с помощью Heavy-Light декомпозиции очевидно. Но в обсуждении поминали какое-то решение за O(N * sqrt(N)) с помощью кластеризации. Можете кто-нибудь объяснить поподробнее?