Родословная: LCA
Вы решили задачу. Теперь можно сравнить подходы.
Предварительно сохраняем предков на степенях двойки, чтобы быстро отвечать на множество запросов.
Авторский разбор для локальной версии на основе условия задачи. Это не выгрузка чужих посылок и не официальное решение исходного сайта.
Ваше принятое решение
Рекомендуемое решение: Двоичные подъёмы
Для каждой вершины запоминаем предков на расстояниях 1, 2, 4 и так далее. Сначала выравниваем глубины скачками, затем одновременно поднимаем обе вершины, пока их непосредственные родители не совпадут. Обход итеративный. Если дерево содержит единственную вершину, её имя берём из запросов; при отсутствии запросов вывод пуст.
n = int(input())
parent = {}
children = {}
for _ in range(n - 1):
child, ancestor = input().split()
parent[child] = ancestor
children.setdefault(ancestor, []).append(child)
children.setdefault(child, [])
q = int(input())
queries = [input().split() for _ in range(q)]
for a, b in queries:
children.setdefault(a, [])
children.setdefault(b, [])
if children:
root = next(name for name in children if name not in parent)
width = max(1, n.bit_length())
depth = {root: 0}
up = {root: [root] * width}
order = [root]
for name in order:
for child in children[name]:
depth[child] = depth[name] + 1
row = [name]
for bit in range(1, width):
row.append(up[row[bit - 1]][bit - 1])
up[child] = row
order.append(child)
for a, b in queries:
if depth[a] < depth[b]:
a, b = b, a
difference = depth[a] - depth[b]
for bit in range(width):
if difference & (1 << bit):
a = up[a][bit]
if a != b:
for bit in range(width - 1, -1, -1):
if up[a][bit] != up[b][bit]:
a, b = up[a][bit], up[b][bit]
a = up[a][0]
print(a)
Время: Ожидаемое O((n + q) log(n + 1)) без учёта длины имён. Память: O(n log(n + 1) + q) записей, включая таблицу предков и сохранённые запросы.
Другой способ: Множество предков первого имени
Сохраняем всю цепочку первого имени вместе с ним самим. Первый общий элемент при подъёме второго имени — самый глубокий общий предок. Этот вариант проще и экономит таблицу подъёмов, но запрос на глубокой цепочке занимает линейное время.
n = int(input())
parent = {}
children = {}
for _ in range(n - 1):
child, ancestor = input().split()
parent[child] = ancestor
children.setdefault(ancestor, []).append(child)
children.setdefault(child, [])
q = int(input())
queries = [input().split() for _ in range(q)]
for a, b in queries:
children.setdefault(a, [])
children.setdefault(b, [])
for a, b in queries:
ancestors = {a}
while a in parent:
a = parent[a]
ancestors.add(a)
while b not in ancestors:
b = parent[b]
print(b)
Время: Ожидаемое O(n + q(h + 1)), h — высота дерева. Память: O(n + q), включая дерево, запросы и множество предков.
На что обратить внимание
- В этой задаче вершина считается собственным предком.
- Ответом может быть одно из двух исходных имён.
Рекомендация учитывает сложность и читаемость для этой задачи. Единственного самого быстрого решения для всех размеров входа и всех компьютеров может не быть.