algorithm - 加权树中两个节点之间的距离

Question

我的问题很直接。

A weighted tree is given. We must find the distance between two given nodes.

由于每次 bfs 超时时查询的数量都非常多(大约 75000)，所以我尝试了不同的方法来做到这一点。

我的算法是这样的:

• 我从顶点 0 运行 dfs 并计算从根 (0) 到所有顶点的距离，类似这样

      depth[v]=depth[u]+w,where u is parent of v and w is weight b/w (u,v)
  

• 一旦我使用 dfs 和每个节点的第 2^j 个父节点计算了所有节点的深度(假设我知道该怎么做)。我为 (u,v) 计算了LCA询问每个查询。

• 然后我这样计算距离

      distance between (u,v)=depth[u]+depth[v]-2*depth[lca(u,v)] 
  

但我没有像预期的那样得到正确的判决。我的算法是正确的还是我遗漏了一些关键的东西。需要指导:)

P.s 如果有人想看我的实现-链接 http://paste.ubuntu.com/13129038/

Answer 1

您的方法听起来很合理，但查看链接代码我建议您尝试一个小示例(例如树中有 3 个节点)并仔细检查父数组的内容。

据我所知，唯一改变父数组内容的行是:

memset(parent,-1,sizeof parent);

和

parent[i][j]=parent[i-1][parent[i-1][j]]

所以我相信 parent 的内容将始终等于 -1。

也许您需要一个基本案例设置 parent[0][j] 等于 j 的父级？

此外，从代码中还不太清楚您是使用深度来表示边数的计数，还是所有边的权重之和。要使距离计算起作用，您需要权重总和，但要使 LCA 算法起作用，您可能会发现需要使用边数。