前言
矩阵乘法优化DP，重链剖分。
涉及到的知识点是比较复杂的，但是比较重要。
这是猫锟在 WC2018 讲的黑科技，一般用来解决树上的带有点权（边权）修改操作的 DP 问题，为了普及，甚至 CSP2022-S T4 考到了此知识点。
做法
朴素DP
设 \(dp_{i,0}\) 表示不选 \(i\)，\(i\) 的子树的最大权独立集的权值大小。
\(dp_{i,1}\) 表示选 \(i\)，\(i\) 的子树的最大权独立集的权值大小。
则有：
\[dp_{i,0}=\sum\limits_{x=1} \max\{dp_{x,0},dp_{x,1}\}\\
dp_{i,1}=\sum\limits_{x=1} dp_{x,0}+a_i
\]
最后答案 \(ans=\max\{dp_{1,0},dp_{1,1}\}\)。
但显然，这个式子如果带修没法跑，复杂度会炸掉，要继续优化。
重链剖分
我们使用重剖优化带修的部分，可以在 \(\Theta(\log^2n)\) 的复杂度下实现单点修改。
将这棵树剖分后，假如有这样一条重链：
设 \(g_{i,0}\) 表示不选择 \(i\) 且只允许选择 \(i\) 的轻儿子所在子树的最大答案，
\(g_{i,1}\) 表示不考虑 \(son_i\) 的情况下选择 \(i\) 的最大答案，
\(son_i\) 表示 \(i\) 的重儿子。
则刚才的方程就简化为：
\[dp_{i,0}=g_{i,0}+\max\{dp_{son_i,0},dp_{son_i,1}\}\\
dp_{i,1}=g_{i,1}+dp_{son_i,0}
\]
最后答案 \(ans=\max\{dp_{rt,0},dp_{rt,1}\}\)。
然后我们现在要考虑如何在线段树内 \(\Theta(1)\) 的修改与查询。
矩阵乘法
我们发现这可以用矩阵乘法优化。