其实很久以前学过一下，大概知道是怎么做的(主要是抄的\(shichengxiao\)的)，但是这次在\(NOIP2018\)考场上推了好久的矩阵，不记得怎么做了，实在是太惨了。
就拿树上最大独立权独立集来说\(dp[u][0]=\sum{max(dp[v][0],dp[v][1])}\),\(dp[u][1]=w[u]+\sum dp[v][0]\), 要求我们修改某个点的\(w[u]\)或者强制某个点选不选。
具体做法就是先树剖，然后先把所有轻儿子的\(dp\)全部转移上来，设\(g_{u,0/1}\),为\(u\)不选或选时亲儿子的贡献，然后假设我们知道了它重儿子的\(dp\)值，我们转移到改点。
构建这样一个矩阵来满足转移：
\[
\left[
\begin{matrix}
g_0 & g_0 \g_1 & -inf \\end{matrix}
\right] *
\left[
\begin{matrix}
dp_{son,0} \dp_{son,1} \\end{matrix}
\right]
\]
然后我们每次改完后，暴力往上跳，修改每一个链顶对其父亲的贡献即可。
原文：https://www.cnblogs.com/dengyixuan/p/10016234.html