Родословная: предки и потомки
Предок содержит всё поддерево потомка; это можно проверить временами обхода.
Как к ней подойти
Потренируйтесь хранить пары «ключ - значение» и находить нужные записи в словаре.
Словарь связывает ключ со значением и позволяет быстро найти запись по ключу. Решите, что будет ключом, что значением и как обрабатывать отсутствующую запись. Для подсчётов удобно начинать с нуля.
Время входа любой вершины поддерева попадает в интервал от входа до выхода его корня. Явный стек обрабатывает глубокие цепочки без рекурсии. Предок здесь строгий: одинаковые имена дают 0. Для единственной вершины имя восстанавливается из запросов.
Проверьте перед запуском
- Не путайте ответ 1 (первое имя — предок) и 2.
- Порядок строк ввода не обязан совпадать с обходом дерева.
Сравните свой подход
Ниже - готовое решение, другой способ, если он есть, и важные детали проверки.
Ваше принятое решение
Рекомендуемое решение: Интервалы итеративного обхода
Время входа любой вершины поддерева попадает в интервал от входа до выхода его корня. Явный стек обрабатывает глубокие цепочки без рекурсии. Предок здесь строгий: одинаковые имена дают 0. Для единственной вершины имя восстанавливается из запросов.
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, [])
enter, leave = {}, {}
if children:
root = next(name for name in children if name not in parent)
stack = [(root, False)]
clock = 0
while stack:
name, exiting = stack.pop()
if exiting:
leave[name] = clock
else:
enter[name] = clock
clock += 1
stack.append((name, True))
for child in children[name]:
stack.append((child, False))
def ancestor(a, b):
return a != b and enter[a] <= enter[b] < leave[a]
for a, b in queries:
print(1 if ancestor(a, b) else 2 if ancestor(b, a) else 0)
Время: Ожидаемое O(n + q) без учёта длины имён. Память: O(n + 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, [])
def ancestor(a, b):
while b in parent:
b = parent[b]
if b == a:
return True
return False
for a, b in queries:
print(1 if ancestor(a, b) else 2 if ancestor(b, a) else 0)
Время: Ожидаемое O(n + q(h + 1)), h — высота. Память: O(n + q) записей.