Контест Senior Деревья обновлено
Сумма расстояний по запросам в дереве
Условие
Дорожная сеть посёлка образует дерево из n перекрёстков. Курьер получил q заказов, для каждого известны перекрёсток склада u и перекрёсток клиента v. Длина маршрута: число дорог на пути между ними. Найдите суммарную длину всех маршрутов.
Ввод: в первой строке n (1 ≤ n ≤ 2500), далее n − 1 строк с рёбрами a b, затем q (1 ≤ q ≤ 2500) и q строк u v (возможно u = v).
Вывод: суммарная длина.
Пример 1
Ввод:
5
1 2
1 3
3 4
3 5
3
4 5
2 4
1 1
Вывод:
5
Пример 2
Ввод:
1
2
1 1
1 1
Вывод:
0
Как подойти
Подсказки: 2
- dist(u, v) = depth[u] + depth[v] − 2·depth[lca].
- Нужен LCA быстрее, чем подъём по одному предку.
Решите в тренажёре
Редактор с автотестами прямо в браузере. Можно решить спокойно, вслух или под таймером, как на собесе.