确定树中两个随机节点之间的距离

Question

鉴于一般的树,我想两个节点之间的距离v和w.

维基百科声明如下:

最低共同祖先的计算可能是有用的,例如,作为确定树中节点对之间距离的过程的一部分:从v到w的距离可以计算为从根到v的距离加上距离从根到w,减去从根到其最低共同祖先的距离的两倍.

假设d(x)表示节点x与我们设置的根的距离1.d(x,y)表示的两个顶点之间的距离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在图上可以看到距离.对于跨越定义的根的任何事物,该算法似乎都失败了.

我错过了什么？

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