前言

今天想补一道题，误以为可以用wqs二分做，于是想先复习一下（好久不用都忘了）；结果找wqs二分例题时输错了题号，发现了一种神奇的dp。。。

题目 洛谷P4719

显然，如果不带修改的话就是一道入门树形dp(设$dp[i][0/1]$分别为以$i$为根的子树，选/不选$i$时的最大权值)

考虑一次对点$p$的修改，对于该修改我们只需要对应修改从$p$到$root$的所有dp值即可，复杂度降低！

但如果数据是一条链，那么$m$次修改的复杂度仍然高达$O(nm)$

现在考虑一个子问题，在序列$a_1,a_2,a_3,...a_n$中，要求选出若干个两两不相邻的数，使得数字和最大，有$m$次修改

显然原题套上树链剖分之后就转化为了上述子问题。

朴素方法

通过广义矩阵乘法可解（详见参考资料）

问题转化为求区间上所有矩阵的积，线段树可解

参考资料

https://www.luogu.com.cn/blog/81844/solution-p4719