我有一棵无根的树,并且给出了形式u和v的查询。我应该计算从u到v的路径查询,就像给出沿路径的权重频率之和。我试图在无根的树中找到lca,但是我却一无所获,因为lca是参照节点计算的。在无根树中,如何继续对权重进行一般操作来解决路径查询?
选择任何顶点为root
。
所有顶点的顶点与root
的存储距离。
[
d[x]
=x
到根的距离
对于距离(a
,b
)= 距离([lca
,a
)+ 距离(lca
,b
)
(d[b] - d[lca(a, b)]) + (d[a] - d[lca(a, b)])