給出一棵樹,求出非空的 權和最大 的子樹。

很輕鬆可以想到 f(u, v),的 dfs_dp 遞迴方法,但是要怎麼存就是個小問題了。

由於 n<16000,無法開 f[n][n] 當 dp數組,所以我用了個小技巧。

因為你知道狀態最多不超過 3*n 種 (邊 (2*n) + f(u, ROOT) (n) = 3*n),所以你可以開一個 pair 來存,每次都用 二分搜 來找 pos 就好了。

雖然會多出一個 lgn,但是因為 n只有16000,也是無傷大雅。

我的code http://codepad.org/OVbGwBkU

 

文章標籤
創作者介紹
創作者 jghs1328 的頭像
jghs1328

jghs1328

jghs1328 發表在 痞客邦 留言(0) 人氣()