樹中兩個節點之間的距離加權

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算法起作用，您可能會發現需要使用邊數。