Linear time algorithm for finding the longest distance between two nodes in a free tree?

Question

Given a free tree, find an algorithm to find the longest path between two nodes that work in linear time. Can this be done if the nodes do not retain their level? If so, how?

If the nodes retain their level, I would move the lower node up the tree to the same level as the other. Than I will continue to move up the tree until the nodes overlap. The distance would be the sum of each time the node was moved up the tree.

Answer 1

, . , , : http://en.wikipedia.org/wiki/Lowest_common_ancestor , : http://en.wikipedia.org/wiki/Tarjan%27s_off-line_least_common_ancestors_algorithm

Answer 2

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, node 0 0.. node 5 5 ..