Условие

В генеалогическом древе определите для двух элементов их наименьшего общего предка (Lowest Common Ancestor). Наименьшим общим предком элементов A и B является такой элемент C, что С является предком A, C является предком B, при этом глубина C является наибольшей из возможных. При этом элемент считается своим собственным предком.

Формат входных данных аналогичен предыдущей задаче

Для каждого запроса выведите наименьшего общего предка данных элементов.

Решение

1. def ancestors(child, p_tree):
2.     result = []
3.     result.append(child)
4.     while child in p_tree:
5.         child = p_tree[child]
6.         result.append(child)
7.     return result
9. p_tree = dict()
10. n = int(input())
11. for i in range(n - 1):
12.     child, parent = input().split()
13.     p_tree[child] = parent
15. m = int(input())
16. for i in range(m):
17.     child_1, child_2 = input().split()
18.     ancestors_for_1 = set(ancestors(child_1, p_tree))
19.     for ancestor in ancestors(child_2, p_tree):
20.         if ancestor in ancestors_for_1:
21.             print(ancestor)
22.             break