CS
Задачник Базовый курс EN

Задача

Самый длинный пролёт

дерево остовное дерево битовые трюки предподсчёт геоданные сети

Города соединены линиями связи, и сеть — дерево: между любыми двумя городами ровно один путь по линиям. Линия между соседними городами — один пролёт, и чем он длиннее, тем дороже его обслуживать и тем вероятнее, что сигнал на нём ослабнет. Для пары городов нужно знать самый длинный пролёт на пути между ними.

Третий тест — настоящие города: все 126 городов и посёлков с населением от 10 000 человек в радиусе 500 км от Алматы (GeoNames), соединённые минимальным остовным деревом; длины пролётов — расстояния по прямой по поверхности Земли в километрах. Спрашивают о каждой паре.

Вход

В первой строке n (1 ≤ n ≤ 100 000). Дальше n − 1 строк a b w — пролёт длиной w между городами a и b (1 ≤ w ≤ 109); вместе они образуют дерево. Затем число вопросов q (1 ≤ q ≤ 50 000) и q строк u v.

Выход

На каждый вопрос — длину самого длинного пролёта на пути из u в v; если u = v, путь пустой, и ответ 0.

Примеры

Пример 1

Вход
5
1 2 5
1 3 9
2 4 3
3 5 2
3
4 5
4 2
3 3
Выход
9
3
0

Пример 2

Вход
6
1 2 40
2 3 75
3 4 20
2 5 60
5 6 90
4
4 6
1 4
6 5
3 1
Выход
90
75
90
75

Ограничения

Время · Python
5000 мс
Время · Go
2000 мс
Память
256 МБ
Проверка
6 тестов

Разбор

Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.

1Подсказка 1

Путь из u в v в дереве — подъём от u к их общему предку и подъём от v к нему же. Максимум на пути — больший из двух максимумов на подъёмах.

2Подсказка 2

В таблице двоичного подъёма хранится, куда ведёт прыжок на 2k шагов. Что ещё можно хранить про этот прыжок, чтобы не перебирать его шаги?

3Идея

Рядом с предком up[k][v] на 2k шагов выше храним most[k][v] — самый длинный пролёт на этих 2k шагах. Прыжок на 2k — два прыжка на 2k−1, поэтому most[k][v] = max(most[k−1][v], most[k−1][up[k−1][v]]). Дальше — обычный поиск общего предка двоичным подъёмом, только каждый прыжок обновляет ответ максимумом своего пролёта.

4Разбор

Подвесим дерево за город 1 обходом в ширину — в порядке обхода родитель всегда раньше ребёнка, и таблицы строятся простыми проходами. most[0][v] — длина пролёта от v к родителю, у корня — 0, и корень сам себе родитель. Вопрос: поднять глубокую вершину на разницу глубин, собирая максимум; если вершины совпали — готово. Иначе прыгать обеими, пока предки разные, собирая максимумы обеих. В конце обе стоят прямо под общим предком, и последние два пролёта — в сам общий предок — нужно добавить отдельно: most[0][a] и most[0][b].

В первом примере путь 4 → 5 — это 4, 2, 1, 3, 5 с пролётами 3, 5, 9, 2. Прыжки довели бы вершины до 2 и 3 с максимумом 3, а самый длинный пролёт, 9 км, — как раз один из двух последних.

Почему в третьем тесте берут минимальное остовное дерево: путь в нём между двумя городами — тот самый путь во всей сети «каждый с каждым», у которого самый длинный пролёт наименьший из возможных. Это следует из свойства разреза, на котором держится минимальное остовное дерево. Самый длинный пролёт на всей сети вокруг Алматы — 203 км.

4+Решение
5Сложность

Подготовка O(n log n) времени и памяти, вопрос — O(log n).

6Типичные ошибки
  • Забытые последние пролёты. После прыжков вершины стоят под общим предком, но два пролёта в него ещё не учтены. Первый пример построен ровно на этом.
  • Подъём по шагу. На глубоких деревьях каждый вопрос стоит высоту дерева; в пятом тесте дерево глубиной около 25 тысяч.
  • Рекурсивный обход. Подвешивать дерево рекурсией в Python нельзя: на дереве глубиной в десятки тысяч стек кончится.

Алгоритмы задачи

GRA Алгоритм Наименьший общий предок Общий предок двух вершин дерева: двоичный подъём за O(log n), обход Эйлера за O(1), Тарьян офлайн. O(log n) на запрос 2 задачи GRA Алгоритм Минимальное остовное дерево Самая дешёвая сеть, связывающая все вершины: Борувка, Краскал и Прим — три способа применить одну лемму. O(E log V) 2 задачи
Каталог алгоритмов