hdu 2647 Reward

題意：

給出一棵樹，求離每個節點最遠的點的距離

思路：

把無根樹轉化成有根樹分析，

對于上面那棵樹，要求距結點2的最長距離，那麼，就需要知道以2為頂點的子樹（藍色圈起的部分，我們叫它Tree（2）），距頂點2的最遠距離L1

還有知道2的父節點1為根節點的樹Tree（1）-Tree(2)部分（即紅色圈起部分），距離結點1的最長距離+dist(1,2) = L2，那麼最終距離結點2最遠的距離就是max{L1，L2}

f[i][0],表示頂點為i的子樹的，距頂點i的最長距離

f[i][1],表示Tree(i的父節點)-Tree(i)的最長距離+i跟i的父節點距離

要求所有的f[i][0]很簡單，隻要先做一次dfs求每個結點到葉子結點的最長距離即可。

然後要求f[i][1], 可以從父節點遞推到子節點，

假設節點u有n個子節點，分别是v1,v2...vn

那麼

如果vi不是u最長距離經過的節點，f[vi][1] = dist(vi,u)+max(f[u][0], f[u][1])

如果vi是u最長距離經過的節點，那麼不能選擇f[u][0],因為這儲存的就是最長距離，要選擇Tree（u）第二大距離secondDist,

可得f[vi][1] = dist(vi, u) + max(secondDist, f[u][1])

貼一段自己AC的代碼：