Родословная: LCA
Предварительно сохраняем предков на степенях двойки, чтобы быстро отвечать на множество запросов.
Как к ней подойти
Потренируйтесь хранить пары «ключ - значение» и находить нужные записи в словаре.
Словарь связывает ключ со значением и позволяет быстро найти запись по ключу. Решите, что будет ключом, что значением и как обрабатывать отсутствующую запись. Для подсчётов удобно начинать с нуля.
Для каждой вершины запоминаем предков на расстояниях 1, 2, 4 и так далее. Сначала выравниваем глубины скачками, затем одновременно поднимаем обе вершины, пока их непосредственные родители не совпадут. Обход итеративный. Если дерево содержит единственную вершину, её имя берём из запросов; при отсутствии запросов вывод пуст.
Проверьте перед запуском
- В этой задаче вершина считается собственным предком.
- Ответом может быть одно из двух исходных имён.
Сравните свой подход
Ниже - готовое решение, другой способ, если он есть, и важные детали проверки.
Ваше принятое решение
Рекомендуемое решение: Двоичные подъёмы
Для каждой вершины запоминаем предков на расстояниях 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), включая дерево, запросы и множество предков.