Блуждание по папкам
В репозитории n папок и файлов, и они образуют дерево: у каждого, кроме корневой папки, есть родительская папка. Робот-индексатор потерял карту и бродит по дереву наугад: из текущей вершины он за один шаг переходит в случайную соседнюю — в родительскую папку или в любой элемент текущей папки, все соседи равновероятны.
Для каждого из q запросов «из u в v» найдите, сколько шагов в среднем пройдёт робот, начав в u, пока впервые не окажется в v.
Вход
В первой строке n (2 ≤ n ≤ 100 000). Во второй — n − 1 чисел: родители вершин 2, 3, …, n; вершина 1 — корень. Дальше q (1 ≤ q ≤ 100 000) и q строк u v (1 ≤ u, v ≤ n).
Выход
Для каждого запроса — среднее число шагов. Оно всегда целое; если u = v, это 0.
Примеры
Пример 1
4 1 1 2 4 4 1 1 4 3 4 2 2
4 8 9 0
Пример 2
5 1 2 3 4 3 5 1 1 5 3 1
16 16 12
Ограничения
- Время · Python
- 8000 мс
- Время · Go
- 2000 мс
- Память
- 256 МБ
- Проверка
- 8 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Путь между двумя вершинами дерева единственный, и робот, чтобы попасть из u в v, обязан пройти все его рёбра по порядку. Значит, ответ — сумма средних времён «перейти с одной вершины пути на следующую». Сколько в среднем идёт робот от вершины до её родителя?
2Подсказка 2
Обозначьте это время H(x) и разберите первый шаг. Из x со степенью d робот с вероятностью 1/d сразу уходит к родителю, а иначе спускается к ребёнку c, должен вернуться в x — это H(c), — и начать заново. Попробуйте лист, потом вершину с двумя листьями: какая формула вырисовывается?
3Идея
Уравнение первого шага: H(x) = 1 + (1/d)·Σc (H(c) + H(x)), где сумма по d − 1 детям. Отсюда H(x)/d = 1 + (1/d)·Σ H(c), то есть H(x) = d + Σ H(c). По индукции от листьев (у листа H = 1) получается H(x) = 2·size(x) − 1, где size(x) — число вершин в поддереве x: действительно, d + Σ(2·size(c) − 1) = 1 + 2·Σ size(c) = 2·size(x) − 1. Ответ целый, как и обещано.
Время спуска от родителя p к ребёнку c — та же формула, если подвесить дерево за c: тогда p — ребёнок c, и в его поддереве все вершины, кроме поддерева c, то есть n − size(c). Получаем 2·(n − size(c)) − 1.
Путь из u в v поднимается до их наименьшего общего предка w и спускается к v. Если заранее посчитать от корня суммы up(x) времён подъёма и down(x) времён спуска по пути до x, ответ — up(u) − up(w) + down(v) − down(w).
4Разбор
Обойти дерево от корня в ширину, размеры поддеревьев посчитать в обратном порядке, суммы up и down — в прямом. Наименьшего общего предка можно искать двоичными подъёмами (так в решении на Go) или офлайн алгоритмом Тарьяна с системой непересекающихся множеств (так в решении на Python: он быстрее в интерпретаторе). Подробно — в статье о наименьшем общем предке.
Пятый тест — настоящие папки и файлы этого сайта: 4701 вершина. От файла routes/web.php до корневой папки робот в среднем доходит за 8 шагов: папка routes маленькая, и подняться из неё легко. А обратно, от корня к этому файлу, — за 18 792 шага: на каждой развилке робот чаще сворачивает не туда и бродит по огромным папкам resources и app.
4+Решение
5Сложность
O(n) на размеры и суммы, O(n log n) на таблицу подъёмов и O(log n) на запрос; у Тарьяна — почти линейно по n + q.
6Типичные ошибки
- 2·size вместо 2·size − 1. Лист добирается до родителя ровно за один шаг, а не за два; на первом же примере ответы расходятся.
- Одна формула в обе стороны. Подъём и спуск по одному ребру стоят по-разному: в сумме они дают 2(n − 1), но поровну делятся, только если поддерево ровно половина дерева.
- Моделирование. Средние тут огромные — в шестом тесте, на пути из 100 000 вершин, от одного конца до другого почти 1010 шагов, — и случайные прогулки не дадут точного целого ответа.
- 32 бита — по той же причине.
Алгоритмы задачи
O(1) на шаг
2 задачи
GRA
Алгоритм
Наименьший общий предок
Общий предок двух вершин дерева: двоичный подъём за O(log n), обход Эйлера за O(1), Тарьян офлайн.
O(log n) на запрос
2 задачи