tioj 1711 Apple Tree [完成]

很久以前就想寫這題了

最近想了一個 O(n^3) 的作法，是引用了樹型DP的概念

可惜時間複雜度還是不對，co了還是TLE

雖然覺得方向沒錯，但卻一直想不到O(n^2)或O(n^2logn)

我後來是用一些怪異的優化才AC的，真的是不太漂亮

但卻完全想不到好作法 = =，有寄信去問學長

後來學長用很神祕的解釋方法使我了解他應該是O( n^2 )

我來說一下我的作法好了

首先從root開始DFS:

對於每一個子樹遞迴後，測試：

1. 走一段路後到那個子樹然後回到當下節點
2. 走一段路後到那個子樹然後就不回來了
3. 先去那個子樹再走一段路然後回到當下節點

[ 每一種步數 * 每一種步數分配 = O(n) ] *（O(n) -> 每一個節點）＝ O( n^2 )

其實要解一個奇怪的方程式吧，就像D&C講義寫的那樣，可是我不會XD

樂正學長的解釋：

最差情況似乎不會超過O(n^2)

平衡2元樹T(n)=2T(n/2)+(n/2)*(n/2)=2T(n/2)+O(n^2)
平衡3元樹T(n)=3T(n/3)+(n/3)*(n/3)+(2n/3)*(n/3)=2T(n/2)+O(n^2)
平衡4元樹T(n)=4T(n/4)+(n/4)*(n/4)+(2n/4)*(n/4)+(3n/4)*(n/4)=2T(n/2)+O(n^2)
鏈狀T(n)=T(n-1)+O(n)

O(n^2)作法：http://codepad.org/4aQpqTWP