Общая папка
В репозитории этого сайта тысячи файлов, разложенных по папкам. Инструменту сравнения нужно для пары файлов быстро находить их ближайшую общую папку — ту, в которой лежат оба, а ни в одной её подпапке оба сразу уже не лежат. Пар много, а дерево папок не меняется.
Дерево задано родителями: узел 1 — корень, у каждого другого узла v родитель pv < v. Узлы — и папки, и файлы. Один из тестов — настоящее дерево исходников этого сайта (папки app, lang, resources, routes и tests на 16 октября 2026 года, 4701 узел), узлы пронумерованы по алфавиту путей.
Вход
В первой строке n (1 ≤ n ≤ 100 000). Во второй — n − 1 чисел p2, …, pn (1 ≤ pv < v); при n = 1 строка пустая. В третьей — число вопросов q (1 ≤ q ≤ 50 000), дальше q строк с номерами узлов u и v.
Выход
На каждый вопрос — номер наименьшего общего предка узлов u и v: самого глубокого узла, который лежит на пути от корня и к u, и к v. Узел считается предком самого себя.
Примеры
Пример 1
8 1 1 2 2 3 5 5 5 6 7 4 8 8 7 3 6 5 5
1 2 5 3 5
Пример 2
1 1 1 1
1
Ограничения
- Время · Python
- 6000 мс
- Время · Go
- 2000 мс
- Память
- 256 МБ
- Проверка
- 7 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Подниматься от обоих узлов к корню, пока они не встретятся, — верно, но столько шагов, какова глубина. Папки бывают вложены на десятки тысяч уровней — по крайней мере в тестах. Нужно свести вопрос о дереве к вопросу о массиве.
2Подсказка 2
Обойдите дерево в глубину и выпишите узлы по порядку обхода. Где в этой записи между узлами u и v оказывается их общий предок или его дети?
3Идея
Общий предок — минимум на отрезке. В обходе Эйлера узел записывается при входе и при каждом возвращении из ребёнка. Между первыми появлениями u и v обход побывает в их общем предке и не поднимется выше него, поэтому общий предок — самый неглубокий узел на этом отрезке записи. Глубины не меняются, и минимум на отрезке даёт разреженная таблица за O(1).
4Разбор
Решение на Go — ровно это: обход Эйлера без рекурсии (стек из пар «узел, следующий ребёнок»), длина записи 2n − 1, первое появление каждого узла, разреженная таблица над позициями записи, сравнивающая глубины.
Решение на Python обходится записью вдвое короче — порядком входа в узлы, n позиций. Пусть u ≠ v и u вошли раньше. Все узлы, в которые вошли после u и не позже v, лежат в поддереве общего предка w, но не равны w: в w вошли раньше u. Среди них есть ребёнок w — тот, через которого идёт путь к v (а если u сам предок v, то ребёнок u на пути к v). Значит, самый неглубокий узел этого отрезка — ребёнок w, и ответ — его родитель. Таблица хранит пары (глубина, узел), упакованные в одно число глубина·(n + 1) + узел, и строится вызовами map(min, …).
4+Решение
5Сложность
Обход — O(n), таблица — O(n log n) времени и памяти, каждый вопрос — O(1). Подъём по родителям — O(глубины) на вопрос: в четвёртом тесте от корня свисают три цепочки по 33 333 узла, и вопросы задают про глубокие узлы из разных цепочек, а в пятом дерево — один путь из ста тысяч узлов.
6Типичные ошибки
- Подъём по родителям. На настоящем дереве сайта он быстр — глубина там меньше десяти, — но на длинных цепочках каждый вопрос стоит десятки тысяч шагов.
- Рекурсивный обход в глубину. На цепочке из ста тысяч узлов рекурсия Python упрётся в предел глубины, а в Go съест стек; нужен явный стек.
- Отрезок по последним появлениям. Брать нужно первые появления (или любые, но тогда отрезок между ними всё равно должен лежать внутри поддерева общего предка); в укороченной записи из n позиций начинать отрезок нужно со следующей после u позиции, иначе ответом окажется сам u.
- Забыть про u = v. Узел — предок самого себя, ответ — он сам.
Алгоритмы задачи
O(1) на запрос, O(n log n) на построение
2 задачи
GRA
Алгоритм
Наименьший общий предок
Общий предок двух вершин дерева: двоичный подъём за O(log n), обход Эйлера за O(1), Тарьян офлайн.
O(log n) на запрос
2 задачи