ツリー内の2つのランダムなノード間の距離を決定する

Question

一般的なツリーが与えられた場合、2つのノードの間の距離はvとwです。

ウィキペディアstates the following：

最下位共通祖先の計算が、ツリー内のノードの対の間の距離を決定するための手順の一部として、例えば、有用であり得る：VからWまでの距離とすることができますルートからvまでの距離と、ルートからwまでの距離から、ルートからそれらの最も低い共通祖先までの距離の2倍を引いたものとして計算されます。

はのはd(x)我々は1に設定されたルートからノードxの距離を示しましょう。 d(x,y)は、2つの頂点xとyの間の距離を示す。 lca(x,y)は、頂点対xとyの最低共通祖先を示します。

従って、4および8,lca(4,8) = 2の場合には、d(4,8) = d(4) + d(8) - 2 * d(lca(4,8)) = 2 + 3 - 2 * 1 = 3です。素晴らしい、それは働いた！しかしながら、上述したケースは、頂点対(8,3)（lca(8,3) = 2）のために失敗すると思わ

d(8,3) = d(8) + d(3) - 2 * d(2) = 3 + 1 - 2 * 1 = 2.これは、しかし、グラフに見られるように距離d(8,3) = 4正しくありません。アルゴリズムは、定義されたルートを越えるものに対しては失敗するようです。

私には何が欠けていますか？適切な2ノード、すなわち1 1右、d(lca(8,2)) == 0、ない場合1

Answer 1

あなたはlca(8,3) = 1であり、= 2ではありません。したがって、それを作るd(1) == 0：

d(8,3) = d(8) + d(3) - 2 * d(1) = 3 + 1 - 2 * 0 = 4 

Answer 2

あなたの導出にそれを持っているとして。この場合のlcaである根からそれ自身までの距離はゼロです。したがって

d(8,2) = d(8) + d(2) - 2 * d(lca(8,2)) = 3 + 1 - 2 * 0 = 4 

2とラベル付けされた2つのノードがあると、混乱する可能性があります。

編集：ノードはもともと2は今、この場合は3をラベルが付いているので、ポストが編集されたは、導出が正しくなりましたが、声明

the distance d(8,2) = 4 as can be seen on the graph 

が間違っている、D（8 、2）= 2