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: