在DP的时候，我们根据一些已知信息，推知局部最优解，再逐步“递推”推出全局最优解。
虽然和动态DP没什么关系但我还想扯一句：DP的时候我们需要保证无后效性——当前状态确定后，之后的状态转移与之前的状态/决策无关。
常规的DP是信息是不能修改的，但我们希望修改信息后，仍然知道全局最优解是多少。而且每次修改的复杂度要比较低
例题：给你一个树，点有点权，求这棵树的最大权独立集是多少——也就是选出一个点集，使得其中点的权值和最大，且这些点之间没有边相连。有m次修改，每次修改一个点的权值，再询问一次答案。
考虑转移方程：
定义f(x,0/1)分别表示x这个点不选/选时，子树内的答案
显然有：
[f(x,0)=sum max(f(v,1),f(v,0)), f(x,1)=sum max(f(v,0))
]
但这个东西修改起来不太好做。。
考虑静态树问题带修改的最经典做法——树链剖分，我们尝试把DP改成可以用树剖维护的形式
额外定义g(x,0/1)表示在x的非重链所有子树中，x不选/选时的总答案
设son表示x的重儿子
[g(x,0)=sum_{v
e son}max(f(v,0),f(v,1)) \
g(x,1)=a_{x}+sum_{v
e son}f(v,0) \
f(x,0)=g(x,0)+max(f(son,0),f(son,1)) \
f(x,1)=g(x,1)+f(son,0) \
]
考虑怎么用矩阵维护它
[egin{bmatrix}
f(x,0)\
f(x,1)
end{bmatrix}
=
egin{bmatrix}
g(x,0) & g(x,0)\
g(x,1) & -inf
end{bmatrix}
*
egin{bmatrix}
f(son,0)\
f(son,1)
end{bmatrix}
]
我们重载了运算符！把*运算换成了+，+运算换成了max
它的运算符合矩阵结合律！可以在线代书第6章找到然而UESTC的线代并没有讲这一章
这么做为什么行？
修改点x的权值时，受影响的只有从x到根的这一条链上的点
中间那个矩阵可以用线段树维护一段矩阵相乘
每次修改，最多涉及到log条树剖链
x的所有祖先中，g函数受影响的只有 x到根路径上经历的每条树剖链和 后一条链岔口的那一个点y。至于变成什么，取决于它后一条链顶点的f函数。
从x所在的树剖链一层层往上推，就能知道根节点的答案，也就是全局答案
那么x所在的链怎么办？路径上某一点的f函数有点难求
每条树剖链的最底端一定是叶节点！
叶节点的f函数是确定的！我们直接问修改前后整条链的答案变化，就能修改y的g函数了