TOJ267 我是一棵樹

最近剛開始使用blogger，先來測試一下，哈哈。

連結：TOJ267 我是一棵樹

題目：

給定一棵N個點的樹，求各點能走到的最遠距離。

做法：

做N次樹直徑的複雜度是O(N^2)，理所當然TLE。
跟社員討論後得到一個方法，用DP的概念可以2次DFS解決。

第一次DFS計算每個點能往葉子走到的最遠&次遠距離。
維護好index&value，做完後，也得到了root的答案

第二次DFS就從root的答案開始往下推，然後你就會發現為何要維護次遠距離了。

上網爬了一下發現用Github Gist貼code最適合我(懶人)了。

code: