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

Question

我的问题非常直截了当。

甲加权树中给出。我们必须找到两个给定节点之间的距离。

因为每次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个父节点（假设我知道该怎么做）。我计算了LCA为（u，v）询问了每个查询。

• 然后我计算方法为距离这样

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

但如预期，我没有得到正确的判决。 是我的算法正确的还是我失去了一些重要的 .Guidance需要:)

诗柜面任何人希望看到我实现链路http://paste.ubuntu.com/13129038/

Answer 1

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

据我可以看到，唯一的线路改变父阵列的内容是：

memset(parent,-1,sizeof parent); 

和

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

因此相信父的内容将总是等于-1 。

也许需要一个碱情况下设置父[0] [j]的等于j的父？

而且，它不是你是否使用深度是指边的数量，或所有边的权重之和的计数从代码很清楚。为了计算距离，您需要一个权重总和，但要使LCA算法起作用，您可能会发现需要使用边数。