完全被這題電翻= =。

dp[0][u][k] 表示 把 u 當 root,走 k 步後回到 u

dp[1][u][k] 表示 把 u 當 root,走 k 步後不回到u

每一個 父結點(u) 到 子結點(v) 都有三種情況:

u->v 後 回到 u

dp[0][u][j+2] = max(dp[0][u][j+2], dp[0][u][k]+dp[0][v][j-k]) //因為 u->v 之間來回 所以 j+2

u->v 後 回到 u 又出去

dp[1][u][j+2] = max(dp[1][u][j+2], dp[1][u][k]+dp[0][v][j-k]) //因為 u->v 之間來回 所以 j+2

u 先去其他子結點  回到 u 又去 v 不回去

dp[1][u][j+1] = max(dp[1][u][j+1], dp[0][u][k]+dp[1][v][j-k]) //因為只有 u->v 所以 j+1

就這樣把整個 樹DP 完成了。

我的code

http://snipt.org/zfUf4

 

文章標籤
創作者介紹

jghs1328

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