用途
对于某些树形dp（目前只会树上最大权独立集或者类似的），动态地修改点权，并询问修改后的dp值
做法（树剖版）
以最大权独立集为例
设$f[x][0/1]$表示x选不选，这棵子树的最大权独立集大小
那么有（设y是x的孩子）
$$f[x][0]=\sum{max\{f[y][0],f[y][1]\}} , f[x][1]=val[x]+\sum{f[y][0]}$$
那么在只关心其中的一个孩子y’的情况下，我们可以得到方程
$$f[x][0]=S_0+max\{f[y’][0],f[y’][1]\},f[x][1]=S_1+f[y’][0]$$
$S_0$和$S_1$的值参照上面的方程，它是与$f[y’][]$无关的
这样的话，我们修改$f[x][]$的值，这个转移的方程不会变 但是这并没有什么卵用
考虑用矩阵优化这个转移，先稍微变化一下转移的形式：
$$f[x][0]=max\{S_0+f[y’][0],S_0+f[y’][1]\},f[x][1]=max\{S_1+f[y’][0],-inf+f[y’][1]\}$$
然后我们发现，如果把矩阵乘法定义中的*变成+,+变成取max（即$c[i,j]=max\{a[i,k]+b[k,j]\}$），就可以把这个式子套进去
（这样做是有道理的，因为max和+满足交换律、结合律，max满足加法分配率）
就是说，x从y转移可以这样：
$$(f[x][0],f[x][1])=(f[y][0],f[y][1])* \left( \begin{matrix} S_0 & S_1 \\ S_0 & -\inf \end{matrix} \right) $$
然而各种孩子们变来变去的，并不能直接用这个
考虑用树剖来做：设$g[x]$为从x的重儿子转移到x的矩阵，为了方便，直接设$g[x][0]=S_0，g[x][1]=S_1$
这样的话，我修改一个点的f值，它的实父亲(?)的g值是不会变的
就是说，改的时候，只有到根的每条链的链顶的父亲的g值会改变（当然x自己的也会改变）
这个变是怎么变的呢，就是
$$g[x][0]+=max\{f_{new}[y][0],f_{new}[y][1]\}-max\{f_{old}[y][0],f_{old}[y][1]\} , g[x][1]+=f_{new}[y][0]-f_{old}[y][0] $$
（y是x的轻儿子）
那么我们改值的一个过程就可以写成这样：
1.求出top[x]原来的f值
2.修改x的g值
3.求出top[x]现在的f值
4.x=top[x]
然后我们发现，叶节点的g值其实就是它的f值，所以我们求一个点的f值的时候直接把矩阵从叶节点乘到这个点就可以了
最后的答案就是根节点的f值取个max
复杂度$O(mlog^2n$)，我的常数好大啊
附代码(luogu4719)
#include<bits/stdc++.h>
#define CLR(a,x) memset(a,x,sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pa;
const int maxn=1e5+,inf=0x3f3f3f3f; inline ll rd(){
ll x=;char c=getchar();int neg=;
while(c<''||c>''){if(c=='-') neg=-;c=getchar();}
while(c>=''&&c<='') x=x*+c-'',c=getchar();
return x*neg;
} struct Mat{
int n,m,a[][];
Mat(int x0=,int x1=,int x2=,int x3=,int x4=,int x5=){
n=x0,m=x1,a[][]=x2,a[][]=x3,a[][]=x4,a[][]=x5;
}
}trans[maxn],g[maxn<<]; //从它的重儿子转移到它
inline Mat operator *(Mat a,Mat b){
if(a.n==) return b;
if(b.n==) return a;
Mat re=Mat(a.n,b.m,-inf,-inf,-inf,-inf);
for(int i=;i<=re.n;i++){
for(int j=;j<=re.m;j++){
for(int k=;k<=a.m;k++){
re.a[i][j]=max(re.a[i][j],a.a[i][k]+b.a[k][j]);
}
}
}return re;
} int N,M,eg[maxn*][],egh[maxn],ect,val[maxn];
int fa[maxn],dep[maxn],dfn[maxn],tot,siz[maxn],wson[maxn],id[maxn],bot[maxn];
int f[maxn][],top[maxn]; inline void adeg(int a,int b){
eg[++ect][]=b,eg[ect][]=egh[a],egh[a]=ect;
} void dfs1(int x){
f[x][]=,f[x][]=val[x];
siz[x]=;
for(int i=egh[x];i;i=eg[i][]){
int b=eg[i][];if(b==fa[x]) continue;
fa[b]=x,dep[b]=dep[x]+;
dfs1(b);siz[x]+=siz[b];
if(siz[b]>siz[wson[x]]) wson[x]=b;
f[x][]+=max(f[b][],f[b][]);f[x][]+=f[b][];
}
int s=f[x][]-max(f[wson[x]][],f[wson[x]][]);
int m=f[x][]-f[wson[x]][];
trans[x]=Mat(,,s,m,s,-inf);
} void dfs2(int x){
dfn[x]=++tot;id[tot]=x;
top[x]=(x==wson[fa[x]])?top[fa[x]]:x;
if(wson[x]) dfs2(wson[x]);
else bot[top[x]]=x;
for(int i=egh[x];i;i=eg[i][]){
int b=eg[i][];if(b==fa[x]||b==wson[x]) continue;
dfs2(b);
}
} inline void build(int p,int l,int r){
if(l==r) g[p]=trans[id[l]];
else{
int m=l+r>>;
build(p<<,l,m);build(p<<|,m+,r);
g[p]=g[p<<|]*g[p<<];
}
} inline void change(int p,int l,int r,int x,int d0,int d1){
if(l==r){
g[p].a[][]+=d0,g[p].a[][]+=d0,g[p].a[][]+=d1;
}else{
int m=l+r>>;
if(x<=m) change(p<<,l,m,x,d0,d1);
else change(p<<|,m+,r,x,d0,d1);
g[p]=g[p<<|]*g[p<<];
}
} inline Mat query(int p,int l,int r,int x,int y){
if(x<=l&&r<=y) return g[p];
else{
int m=l+r>>;Mat re=Mat();
if(y>=m+) re=query(p<<|,m+,r,x,y);
if(x<=m) re=re*query(p<<,l,m,x,y);
return re;
}
} inline int update(int x,int y){
Mat od,nw;
while(x){
int a,b;
if(y) a=,b=y,y=;
else{
a=max(nw.a[][],nw.a[][])-max(od.a[][],od.a[][]);
b=nw.a[][]-od.a[][];
}
od=query(,,N,dfn[top[x]],dfn[bot[top[x]]]);
change(,,N,dfn[x],a,b);
nw=query(,,N,dfn[top[x]],dfn[bot[top[x]]]);
x=fa[top[x]];
}
return max(nw.a[][],nw.a[][]);
} int main(){
//freopen("","r",stdin);
int i,j,k;
N=rd(),M=rd();
for(i=;i<=N;i++)
val[i]=rd();
for(i=;i<N;i++){
int a=rd(),b=rd();
adeg(a,b);adeg(b,a);
}
dep[]=;dfs1();
dfs2();build(,,N);
for(i=;i<=M;i++){
int a=rd(),b=rd();
printf("%d\n",update(a,b-val[a]));
val[a]=b;
}
return ;
}
