luogu P4719 【模闆】"動态 DP"&動态樹分治

題面傳送門

發現一直口胡的ddp是錯的

首先不難想到普通的dp:設\(dp_{i,0}\)表示不選這個點的答案，設\(dp_{i,1}\)為選這個點的答案。

得到\(dp_{i,0}=\sum\limits_{(i,j)\in E}{\max(dp_{j,0},dp_{j,1})}\)

\(dp_{i,1}=\sum\limits_{(i,j)\in E}{dp_{j,0}+A_i}\)

然後對這個樹樹鍊剖分。

設\(g_{i,0}\)表示這個點不選的且不考慮重鍊的答案，設\(g_{i,1}\)表示這個點選且不考慮重鍊的答案。

那麼設\(i\)的重鍊為\(j\)，那麼\(dp_{i,0}=g_{i,0}+\max(dp_{j,0},dp_{j,1}),dp_{j,1}=g_{i,1}+dp_{j,0}\)

然後構造個廣義矩陣乘法重鍊直接維護輕邊暴力修改就好了。

code: