如何在无根树中执行路径查询?

问题描述 投票:0回答:1

我有一棵无根的树,并且给出了形式u和v的查询。我应该计算从u到v的路径查询,就像给出沿路径的权重频率之和。我试图在无根的树中找到lca,但是我却一无所获,因为lca是参照节点计算的。在无根树中,如何继续对权重进行一般操作来解决路径查询?

algorithm data-structures graph tree graph-algorithm
1个回答
0
投票

选择任何顶点为root

所有顶点的顶点与root的存储距离。

[d[x] = x到根的距离

对于距离ab)= 距离([lcaa)+ 距离lcab

]

(d[b] - d[lca(a, b)]) + (d[a] - d[lca(a, b)])

© www.soinside.com 2019 - 2024. All rights reserved.