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

Паводок

дерево дерево отрезков запросы на отрезке граф геоданные наука и физика

Гидрологи следят за паводком на горной сети стока. Сеть — это n клеток, и из каждой вода стекает в одну соседнюю, ниже по течению, или уходит с карты. Потоки не сливаются в круг: от любой клетки вода рано или поздно уходит.

Приходят два вида сообщений. Ливень: в клетку v выпало x единиц воды, и они прибавляются к расходу самой клетки v и всех клеток ниже по течению, до места, где вода уходит с карты. Вопрос: каков наибольший расход на пути по руслам между клетками a и b? Путь по руслам — это путь в дереве стока: вверх от одной клетки до места, где сливаются потоки обеих, и вниз ко второй.

Третий тест — сеть стока гор над Алматы, посчитанная по рельефу NASA SRTM, как в статье: 28 341 клетка. В четвёртом — одна река из ста тысяч клеток.

Вход

В первой строке n (1 ≤ n ≤ 10⁵). Во второй — n чисел p₁, …, p_n: клетка v стекает в клетку p_v, а p_v = 0 значит, что из v вода уходит с карты. Затем число сообщений q (1 ≤ q ≤ 10⁴) и q строк: 1 v x — ливень (1 ≤ x ≤ 1000) или 2 a b — вопрос. В вопросе вода из a и из b уходит с карты через одну и ту же клетку; a может совпадать с b. Сначала расход всех клеток — ноль.

Выход

На каждый вопрос — одно число: наибольший расход среди клеток пути от a до b, включая их самих.

Примеры

Пример 1

Вход

7
0 1 2 3 2 5 3
7
1 4 5
1 6 2
2 4 6
1 7 4
2 7 1
2 4 4
2 6 5

Выход

Пример 2

Вход

6
0 1 1 0 4 5
6
1 2 3
1 6 7
2 2 3
2 6 4
1 3 1
2 3 2

Выход

3
7
4

Ограничения

Время · Python: 4000 мс
Время · Go: 1000 мс
Память: 256 МБ
Проверка: 9 тестов

Разбор

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

1Подсказка 1

Ливень меняет расход на целом пути от клетки до края, вопрос спрашивает о целом пути между двумя клетками. Сколько клеток в таком пути на реке из ста тысяч клеток, как в четвёртом тесте? А сколько сообщений?

2Подсказка 2

Если бы дерево было одной цепочкой, хватило бы дерева отрезков: прибавить на отрезке, максимум на отрезке. Можно ли разрезать любое дерево на цепочки так, чтобы любой путь задевал их немного?

3Идея

Тяжёлые пути. У каждой клетки выбираем тяжёлого ребёнка — приток с самым большим бассейном, — и нумеруем клетки обходом в глубину, заходя в тяжёлого ребёнка первым. Тогда каждый тяжёлый путь — отрезок номеров, а путь между любыми двумя клетками режется на O(log n) таких отрезков: подъём по лёгкому ребру больше чем удваивает размер поддерева. Над номерами — дерево отрезков с прибавлением на отрезке и максимумом.

4Разбор

Ливень в v — это путь от v до корня её дерева: поднимаемся по головам цепочек и на каждом куске прибавляем x на отрезке номеров от головы до текущей клетки. Вопрос о пути a–b — тот же подъём, но всякий раз из той клетки, у которой голова цепочки глубже; когда головы совпали, остаётся отрезок между номерами a и b. Ответ — наибольший из максимумов по всем отрезкам.

Дерево отрезков удобно писать снизу вверх, без рекурсии: у каждого узла — максимум его отрезка с учётом прибавок, висящих на нём самом, и сама висящая прибавка. Прибавление на отрезке кладёт прибавку в O(log n) узлов и пересчитывает их предков; перед вопросом висящие прибавки на двух путях от корня к концам отрезка проталкиваются вниз. Дерево стока может быть лесом: у каждой клетки, откуда вода уходит, свой обход и свои цепочки.

4+Решение

5Сложность

Подготовка O(n). Каждое сообщение — O(log n) отрезков номеров по O(log n) в дереве отрезков, всего O(q log² n). На реке-цепочке отрезок вообще один.

6Типичные ошибки

По клеткам. Ливень проходит все клетки ниже по течению, вопрос поднимается от обоих концов. Это wrong.py: ответы верные, но на реке из ста тысяч клеток каждый ливень в истоке — сто тысяч шагов, и десять тысяч сообщений не укладываются во время.
Рекурсия. Обход в глубину рекурсией упадёт на четвёртом тесте: глубина дерева — сто тысяч.
Подъём не из той клетки. Подниматься надо из той клетки, чья голова цепочки глубже, а не из более глубокой клетки, иначе можно проскочить место слияния потоков.
Тяжёлый ребёнок по глубине. Если продолжать цепочку в самый глубокий приток, а не в самый большой, отрезков на пути бывает порядка √n.

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

GRA Алгоритм Тяжёлые пути Запросы на путях дерева: тяжёлые пути режут любой путь на O(log n) отрезков массива под деревом отрезков. O(log² n) на запрос 1 задача DS Структура данных Дерево отрезков Минимум, максимум и сумма на любом отрезке с изменениями на ходу: оба действия за O(log n). O(log n) на запрос и на изменение 2 задачи