Экскурсия по дереву жизни
По дереву жизни водят экскурсии: от одного таксона к другому, всегда кратчайшей дорогой — вверх к их общему предку и вниз ко второму. На каждом шаге экскурсовод рассказывает о таксоне, у которого стоит группа. Куда группа придёт через k шагов?
Дерево задано родителями: вершина 1 — корень, у каждой другой вершины v родитель pv < v. Третий тест — дерево жизни из статьи: все виды млекопитающих из таксономии NCBI и дюжина ориентиров из остальной жизни, 7865 таксонов в прямом порядке обхода, корень — «клеточные организмы».
Вход
В первой строке n (1 ≤ n ≤ 100 000). Во второй — n − 1 чисел p2, …, pn (1 ≤ pv < v); при n = 1 строка пустая. В третьей — число экскурсий q (1 ≤ q ≤ 50 000), дальше q строк u v k (1 ≤ u, v ≤ n, 0 ≤ k ≤ 2n).
Выход
На каждую экскурсию — номер вершины, в которой окажется группа через k шагов кратчайшего пути из u в v (при k = 0 это сама u), или −1, если путь короче k шагов.
Примеры
Пример 1
7 1 1 2 2 3 6 4 4 7 0 4 7 2 4 7 5 5 5 1
4 1 7 -1
Пример 2
7 1 2 3 3 5 1 5 6 2 3 2 6 3 7 4 4 4 7 6 5 5 0
2 6 4 -1 5
Ограничения
- Время · Python
- 4000 мс
- Время · Go
- 2000 мс
- Память
- 256 МБ
- Проверка
- 6 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Кратчайший путь из u в v в дереве идёт через их наименьшего общего предка c. Сколько в нём шагов и сколько из них — вверх?
2Подсказка 2
Если k-й шаг пришёлся на спуск к v, удобнее считать его с другого конца: на сколько шагов он выше v?
3Подсказка 3
В пятом тесте дерево высотой в десятки тысяч. Подниматься по одному шагу на каждый вопрос — миллиарды шагов. Что нужно уметь быстро, кроме общего предка?
4Идея
Путь — это a = depth(u) − depth(c) шагов вверх и b = depth(v) − depth(c) шагов вниз. Если k ≤ a, ответ — предок u на k шагов выше. Если a < k ≤ a + b, ответ лежит на спуске, и он — предок v на a + b − k шагов выше. Иначе −1. Обе операции — общий предок и «предок на s шагов выше» — даёт одна таблица двоичного подъёма: подъём на s — по прыжку на каждый единичный бит s.
5Разбор
Родители идут раньше детей, поэтому глубины и таблица up[j][v] — предок на 2j шагов — считаются простыми проходами по массиву, без обхода в глубину. Корень делаем своим собственным родителем: прыжок выше корня приводит в корень, и таблица не выходит за край. Функция climb(v, s) прыгает по единичным битам s; lca(u, v) поднимает глубокую вершину climb-ом на разницу глубин и прыгает обеими, пока предки разные. Дальше — три случая из идеи.
В примере путь 4 → 7 проходит 4, 2, 1, 3, 6, 7: два шага вверх до 1 и три вниз. Шаг 2 — сама вершина 1, шаг 5 — 7, шага 6 нет.
5+Решение
6Сложность
Подготовка O(n log n), каждый вопрос O(log n): общий предок и один подъём.
7Типичные ошибки
- Подъём по одному шагу. Верен, но на глубоких деревьях каждый вопрос стоит столько шагов, сколько в дереве уровней; пятый тест такое решение не проходит по времени.
- Спуск, отсчитанный от общего предка. Вниз по дереву идти некуда: у вершины много детей. Шаг на спуске ищут подъёмом от v.
- Граница пути. При k = a + b ответ — сама v, а при k = a — сам общий предок; −1 только при k > a + b.