樹DP,難度較低的一題。

先 dfs_dp 求出以 u 為樹根的樹權和,ans=min{sum-2*dp[u->v]}。

說明一下,假設切成 u, v 為根的兩棵樹(其中u->v),sum=dp[u]+dp[v],得dp[u]-dp[v]=sum-2*dp[v]。

我的code

http://codepad.org/RZrgkj0r

p.s: long long 小心。

 

 

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

jghs1328

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