Алгоритм линейного времени для нахождения наибольшего расстояния между двумя узлами в свободном дереве?

Question

Учитывая свободное дерево, найдите алгоритм, чтобы найти самый длинный путь между двумя узлами, который работает за линейное время.Возможно ли это сделать, если узлы не сохраняют свой уровень?Если да, то как?

Если узлы сохраняют свой уровень, я бы переместил нижний узел вверх по дереву на тот же уровень, что и другой.Чем бы я продолжал двигаться вверх по дереву, пока узлы не перекрываются.Расстояние будет суммой каждого перемещения узла вверх по дереву.

Answer 1

Я решил http://www.spoj.pl/problems/PT07Z/ со следующим кодом в качестве упражнения для изучения Python:

def func(node):
    global M
    if (len(node)==0):
        return 0
    else:
        s=[func(nodes[n]) for n in node]
        s.sort()
        m1=s[-1]+1
        m2=0
        if len(s)>1:
            m2=s[-2]+1
        M=max(M,m1+m2)
        return m1

t=input()
nodes={}
for node in range(1,t+1):
    nodes[node]=[]
for i in range(t-1):
    s=raw_input().split()
    a,b=int(s[0]),int(s[1])
    nodes[a].append(b)

M=0
func(nodes[1])
print M

Обратите внимание, что вы можете сортировать узлы по линейному времени, потому что вы знаете, что узлы переходят от 0 к N, поэтому вы перемещаете узел 0 в положение 0 .. узел 5 в положение 5 и т. Д.

Answer 2

Если все ребра между двумя узлами не могут быть использованы более одного раза, путь является фиксированным. Итак, проблема в том, чтобы найти наименьшего общего предка, вы можете прочитать здесь: http://en.wikipedia.org/wiki/Lowest_common_ancestor Есть знаменитый алгоритм для его решения, и он здесь: http://en.wikipedia.org/wiki/Tarjan%27s_off-line_least_common_ancestors_algorithm