フリーツリー内の2つのノード間の最長距離を求める線形時間アルゴリズム？

Question

フリーツリーが与えられた場合、線形時間で実行される2つのノード間の最長経路を見つけるアルゴリズムを見つけます。ノードがレベルを保存していない場合、これは可能ですか？はいの場合、どうですか？

ノードがレベルを格納している場合は、ツリーの上にある下位ノードを同じレベルに移動します。ノードが重なるまで私はツリーを上に移動し続けます。距離は、ノードがツリーの上に移動したときの合計です。

Answer 1

2つのノード間のすべてのエッジを複数回使用できなかった場合、パスは固定されます。だから、問題は最小の共通の祖先を見つけることです、あなたはここで読むことができます：http://en.wikipedia.org/wiki/Lowest_common_ancestor が、それを解決するための有名なアルゴリズムです、それはここにある： http://en.wikipedia.org/wiki/Tarjan%27s_off-line_least_common_ancestors_algorithm

Answer 2

私のpythonを学ぶための演習として、次のコードでhttp://www.spoj.pl/problems/PT07Z/を解きます：

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 

（注）ノードがNに0から行く知っているので、あなたは線形時間内のノードを並べ替えることができますので、あなたは、位置など5私は