Как решить эту проблему?

Question

У меня есть дерево п вершин n<=10^5, где каждая вершина имеет счет [I] и д запросы q<=10^5 Каждый запрос имеет два параметра и и L, мне нужно найти

sum(score[i]) for all i where lca(i,u)=u and dist(u,i)=L 

я могу решить каждый запрос в O(n) время с использованием bfs, но это не эффективно. Как я могу это оптимизировать? Я потратил много времени на это, но не смог найти способ решить его в nlogn времени для всех запросов.

Любая помощь приветствуется. Спасибо

Answer 1

Дайте u быть на глубине h. Тогда нам нужно найти сумму баллов всех вершин на глубине h + L в поддереве u (это просто переформулировка проблемы).

1. Сохраним вектор вершин, отсортированных по времени входа для каждого уровня.

2. Поддерево смежного сегмента в векторе для глубины h + L.

3. Мы можем найти его границы, используя двоичный поиск (что-то вроде lower_bound(at_depth[h + L].begin(), at_depth[h + L].end(), entrance_time[u]), upper_bound(at_depth[h + L].begin(), at_depth[h + L].end(), leave_time[u]) в C++).

4. Ответ - сумма баллов в этом диапазоне. Мы можем найти его в O(1) с использованием префиксных сумм.

Это решение требует двоичного поиска и два префикса суммы выглядят взлетов на запрос, поэтому он работает в O(log N) времени.