Как вычислить наименьшего общего предка во времени NlogN, используя динамическое программирование на python

Question

Это домашнее задание.

Входные данные: словарь списков, где каждый ключ является узлом, а значение - списком родителей узла. Пустой список означает, что узел является корнем.

{'1': ['3'], '2': ['3'], '4': ['5'], '3': ['5'], '6': ['7'], '8': ['7'], '7': ['9'], '5':['9'], '9':[]}

Вывод: словарь словарей, где каждый ключ - это узел i, а значение - это словарь, где каждый ключ - это узел j, а значение - это наименьший общий предок. Это сделано для всех узлов.

{'1': {'1': {'1'}, '9': {'9'}, '5': {'5'}, '3': {'3'}, '2': {'3'}, '4': {'5'}, '7': {'9'}, '6': {'9'}, '8': {'9'}}, '2': {'9': {'9'}, '5': {'5'}, '3': {'3'}, '1': {'3'}, '2': {'2'}, '4': {'5'}, '7': {'9'}, '6': {'9'}, '8': {'9'}}, '4': {'9': {'9'}, '5': {'5'}, '3': {'5'}, '1': {'5'}, '2': {'5'}, '4': {'4'}, '7': {'9'}, '6': {'9'}, '8': {'9'}}, '3': {'9': {'9'}, '5': {'5'}, '3': {'3'}, '2': {'3'}, '4': {'5'}, '7': {'9'}, '6': {'9'}, '8': {'9'}, '1': {'3'}}, '6': {'9': {'9'}, '5': {'9'}, '3': {'9'}, '1': {'9'}, '2': {'9'}, '4': {'9'}, '6': {'6'}, '7': {'7'}, '8': {'7'}}, '8': {'9': {'9'}, '5': {'9'}, '3': {'9'}, '1': {'9'}, '2': {'9'}, '4': {'9'}, '7': {'7'}, '6': {'7'}, '8': {'8'}}, '7': {'9': {'9'}, '5': {'9'}, '3': {'9'}, '1': {'9'}, '2': {'9'}, '4': {'9'}, '7': {'7'}, '8': {'7'}, '6': {'7'}}, '5': {'9': {'9'}, '5': {'5'}, '3': {'5'}, '2': {'5'}, '4': {'5'}, '7': {'9'}, '6': {'9'}, '8': {'9'}, '1': {'5'}}, '9': {'9': {'9'}, '5': {'9'}, '3': {'9'}, '2': {'9'}, '4': {'9'}, '7': {'9'}, '6': {'9'}, '8': {'9'}, '1': {'9'}}}

Алгоритм, который мы используем, должен быть алгоритмом динамического программирования, поэтому после небольшого исследования я обнаружил, что это можно сделать с временной сложностью NlogN, используя предварительный предварительный расчет разреженной таблицы для каждого 2-го предка узла i. Затем следует проверка, чтобы увидеть, находятся ли узел i и узел j на одном уровне, а если нет, то сделать их равными, если узлы i и j равны, то мы закончили, но если нет, то нам нужно найти x так, что x-й родитель узла i совпадает с x-м родительским узлом j. Поэтому, чтобы сделать это, я знаю, что должен найти наибольшее значение k (которое является разницей между глубинами двух узлов), чтобы 2^k-й родитель i и j отличался, а затем обновить i и j, чтобы они стали этими родителями., Мы продолжаем до тех пор, пока i и j не окажутся на одном уровне (k = 0), а затем мы узнаем, что узлы i и j находятся чуть ниже LCA, поэтому мы можем просто взять в качестве ответа родителя любого узла.

Теперь моя проблема в том, что... Я понимаю алгоритм, и я видел и прочитал множество учебных пособий с кодом /puesdocode о том, как это сделать, и я до сих пор не могу реализовать это в Python. До сих пор я был в состоянии только вычислить разреженную матрицу (что, честно говоря, я не совсем уверен, что это правильно), но я не знаю, как вычислить глубину каждого узла, чтобы продолжить. Я надеюсь, что кто-то может найти время, чтобы провести меня по алгоритму.

Вот моя функция для создания разреженной матрицы, где p - входной словарь, описанный выше.

def preprocess(p=p):
    P = [[-1 for i in range(0, len(p) + 1)] for j in range(0, len(p) + 1)]
    for i in range(1, len(p) + 1):
        P[i][0] = p[str(i)]
        if P[i][0] == []:
            P[i][0] = [str(i)]
    for j in range(1, len(p) + 1):
        if (1 << j) < len(p):
            for i in range(1, len(p) + 1):
                if P[i][j-1] != -1:
                    inside = int(P[i][j-1][0])
                    P[i][j] = P[inside][j-1]
    return 

РЕДАКТИРОВАТЬ: Может быть полезно добавить, у меня на самом деле нет опыта программирования хе. Я био-майор, который по глупости решил пройти курс обучения вне своей стихии.