引入——最大权独立集问题：
最大权独立集：对于一棵树，求出一个点集，这个点集里面的任意两个点都不相连。那么在所有这样的点集中，点权和最大的那个点集，就被成为最大权独立集。
想要求出最大权独立集的点权和，我们只需要使用树上dp的方法即可实现
设数组f[N][2]
其中f[x][0]表示不选择节点x加入点集，以x为根的这棵树的最大点权和
f[x][1]表示选择x加入点集，以x为根的这棵树的最大点权和
假设父结点为x,子结点为
那么我们就可以得到转移方程：
其中a[x]表示x节点的点权
转移方程的含义是：
如果不选x结点，那么对于他的每个子结点v，我们可以选也可以不选，只要选择两者中点权更大的就可以了
如果选择x节点，那么对于他的每个子结点，我们一定不能选，所以只能选择f[v][0]，这里可以保证f[v][0]>=0（因为它是由第一条转移方程转移得到的）
这是一条子节点向父结点转移的方程，因此，我们只需要对树的根节点进行dfs,先更新子节点的值，再用其来更新父节点的值，最终就可以得到根的两个dp值，f[root][0]和f[root][1]，我们只需要取两者中的较大者，就是该棵树的最大权独立集
动态DP：
题目链接：https://www.luogu.com.cn/problem/P4719
什么为动态DP？
上面我们对一棵静态（点权不会被修改）的树进行了DP，得到了答案。
但如果我们这个时候对树上的某一个结点的点权进行了修改，显然这棵树的最大权独立集点权和可能会发生改变，我们这个时候怎么再次求得答案呢？
一种最容易想到的方法就是对整棵树再dp一次，显然如果修改的次数和询问的次数很多的时候，这种方法的效率就会变得很差
我们对一个结点进行修改，其实它并不会影响到整棵树中每一个节点的dp值，也就是说，我们只需要对需要dp值的节点进行修改就可以了，难点就在于我们怎么找出这些结点
我们可以想象一下，我们现在对结点u进行了点权修改，显然u的子树的dp值是不需要修改的，u的兄弟结点的dp值也是不需要修改的，我们需要修改的只有u节点到根结点这一整条路径上的结点的dp值
那既然是这样的话，我们直接记录每个结点的深度，然后修改节点的时候逐步向上爬到根pushup不就好了吗？
诚然这样也可以，但如果要修改的节点深度很深，那每一次修改需要遍历的结点也还是很多，效率也还不够高
树链剖分：
这里对于处理结点到根路径上的区间修改问题，我们想到了使用树链剖分+线段树来维护这个区间
我们这里对这棵树进行树链剖分，分成轻链与重链
这样，每一条重链上的结点的dfs序都形成一段连续的区间
现在问题就在于，怎么去维护这个区间的dp值
广义矩阵乘法：
这个区间要维护的值并不是简单的加和或者乘积的形式
对于轻重链剖分的特点
我们再引入两个数值：
对于结点x，我们引入g0和g1
g0——不选择x结点，选择或者不选择x结点的轻儿子的最大点权和
g1——选择x节点，完全不选择x节点的轻儿子的最大点权和
那么我们再联系上刚刚的f[N][2]数组，我们就有关系：
我们对其进行转化一下，得到
联系之前的广义矩阵乘法
我们得到：
那我们对每一个节点都构造这样的一个矩阵：
而对于每条重链来说，其链尾结点一定是叶子结点，对于这样的节点v
我们有：
f[v][0]==g0==0, f[v][1]==g1==a[v]
我们假设这条重链上u的父结点为u
我们令结点u的矩阵与结点v的矩阵广义相乘
有：
我们将p结点带g和带f的矩阵用g(p)和f(p)来简化表示
那么假设现在根节点1所在重链依次有节点1,2,4,5
于是f(1)=g(1)*g(2)*g(4)*g(5)=g(1)*g(2)*g(4)*f(5)=g(1)*g(2)*f(4)=g(1)*f(2)=f(1)
通过对整个重链区间进行矩阵广义乘积和，我们得到了f(1)矩阵，进而可以得到整棵树的最大权独立集点权和
因此我们只需要以每个结点的dfs序为区间下标建立一棵线段树，线段树的权值为区间矩阵广义乘积和，每次对一个结点进行修改的时候，只需要维护这个节点所在的重链区间以及这个节点到根结点的重链区间的矩阵广义乘积和即可，这样，我们就把修改的时间复杂度从n降低到了logn
而查询的时候，我们只需要求出根节点所在重链的区间广义乘积，那么答案就是max(f[root][0],f[root][1])
实现代码如下：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 1E5 + 10, INF = (1 << 30);
#define ls (u<<1)
#define rs (u<<1|1)
#define mid (l+r>>1)
//a:各个点的权值
int n, m, a[N];
//链式前向星
int to[N << 1], nxt[N << 1],h[N] ,idx;
void add(int a,int b){
to[++idx] = b;
nxt[idx] = h[a];
h[a] = idx;
}
//fa:父亲节点
//siz:子树大小
//son:重儿子
//f[x][0]:对于x而言，不选x的最大权独立集
//f[x][1]:对于x而言，选x的最大权独立集
int fa[N], siz[N], son[N], f[N][2];
//dfn:dfs序
//id:节点编号
//top:链头结点
//bot:链尾序号
int dfn[N], id[N], top[N], bot[N], tot;
//树剖fa,siz,son,f
void dfs1(int x)
{
siz[x] = 1;
//选x的最大权独立集初始化为a[x]
f[x][1] = a[x];
for (int i = h[x], y; y = to[i];i=nxt[i]){
if(y==fa[x])
continue;
fa[y] = x;
dfs1(y);
siz[x] += siz[y];
//更新重儿子
if(siz[y]>siz[son[x]])
son[x] = y;
//如果不选x，那么就是加上选儿子或者不选儿子的最大权独立集
f[x][0] += max(f[y][0], f[y][1]);
//选x，就加上不选儿子的最大权独立集（显然不选儿子的最大权独立集不会小于0）
f[x][1] += f[y][0];
}
}
//树剖dfn,id,top,bot
void dfs2(int x,int tp){
//更新dfs序
dfn[x] = ++tot;
//更新结点编号
id[tot] = x;
//更新top
top[x] = tp;
//更新这条链的链尾结点
bot[tp] = tot;
//先dfs重儿子
if(son[x])
dfs2(son[x], tp);
//再dfs轻儿子
for (int i = h[x], y; y = to[i];i=nxt[i]){
if(y==fa[x]||y==son[x])
continue;
dfs2(y, y);
}
}
struct matrix{
int g[2][2];
matrix operator&(const matrix &b) const{
matrix tmp;
memset(tmp.g, -0x3f, sizeof(tmp.g));
for (int k = 0; k < 2;k++){
for (int i = 0; i < 2;i++){
for (int j = 0; j < 2;j++){
tmp.g[i][j] = max(tmp.g[i][j], g[i][k] + b.g[k][j]);
}
}
}
return tmp;
}
} mt[N], tr[N << 2];
//节点g矩阵
//线段树g矩阵及其乘积
//建线段树
//g0表示不选x结点，选或不选x的轻儿子的最大权独立集
//g1表示选x结点，全不选x的轻儿子的最大权独立集
//y表示x的重儿子
//则f[x][0]=max(f[y][0]+g0,f[y][1]+g0)
//f[x][1]=max(g1+f[y][0],-INF)
void build(int u,int l,int r){
if(l==r){
//g0:不选x
//g1:选x
//x是线段树区间下标所对应的节点编号
int x = id[l], g0 = 0, g1 = a[x];
for (int i = h[x], v; v = to[i];i=nxt[i]){
if(v!=fa[x]&&v!=son[x]){
//g0:对轻儿子选或不选
g0 += max(f[v][0], f[v][1]);
//g1：全不选轻儿子
g1 += f[v][0];
}
}
//更新线段树
//线段树叶子结点的矩阵就等于这个节点的矩阵
tr[u] = mt[x] = {g0, g0, g1, -INF};
return;
}
build(ls, l, mid);
build(rs, mid + 1, r);
//pushup
//着重理解为什么可以用广义矩阵乘法pushup
tr[u] = tr[ls] & tr[rs];
}
//单点修改
void change(int u,int l,int r,int p){
//找到了点
if(l==r){
//把叶子节点的矩阵修改为
//区间下标所对应的节点的矩阵
tr[u] = mt[id[l]];
return;
}
if(p<=mid){
change(ls, l, mid, p);
}
else{
change(rs, mid + 1, r, p);
}
tr[u] = tr[ls] & tr[rs];
}
//区间查询
//查询出以区间x到y的这条重链的矩阵乘积，那么max(g[0][0],g[1][0])就是以id[x]结点为根的最大权独立集
matrix query(int u,int l,int r,int x,int y){
//找到了对应的区间，返回矩阵
if(x==l&&r==y)
return tr[u];
//如果区间完全属于左树，递归左边
if(y<=mid){
return query(ls, l, mid, x, y);
}
//如果区间完全属于右树，递归右边
if(x>mid)
return query(rs, mid + 1, r, x, y);
//否则的话，说明目标区间和左右子树的区间都有交集
//递归查找左右子树，并更新目标区间
return query(ls, l, mid, x, mid) & query(rs, mid + 1, r, mid + 1, y);
}
//修改点权
void update(int u,int v){
//修改u结点的点权
//把u结点原来的a[u]权值修改为v权值
mt[u].g[1][0] += v - a[u];
a[u] = v;
//当u结点存在的时候
while(u){
//查询以u结点为根的矩阵
matrix a = query(1, 1, n,dfn[top[u]], bot[top[u]]);
//更新线段树中的矩阵
change(1, 1, n, dfn[u]);
//再查询一次u结点的矩阵
matrix b = query(1, 1, n, dfn[top[u]], bot[top[u]]);
//u结点跳到另一条重链上，继续更新别的重链，一直到含根结点的重链
u = fa[top[u]];
//修改这条重链的父结点的矩阵
//由于更新了这条重链中的某一个结点的权值,那么对于这条重链（相对于它的父亲，它是轻儿子）
//那么就有公式:
//max(b.g[0][0],b.g[1][0]):选这个轻儿子或者不选
//max(a.g[0][0],a.g[1][0])：之前选了这个亲儿子或者不选（减去它就相当于没选过）
mt[u].g[0][0] += max(b.g[0][0], b.g[1][0]) - max(a.g[0][0], a.g[1][0]);//更新这个节点的g0
mt[u].g[0][1] = mt[u].g[0][0];//更新矩阵中的g0
//必须不选轻儿子
mt[u].g[1][0] += b.g[0][0] - a.g[0][0];//更新g1
}
}
int main(){
scanf("%d%d", &n, &m);
int x, y;
for(int i = 1; i <= n;i++){
scanf("%d", a + i);
}
for (int i = 1; i < n;i++){
scanf("%d%d", &x, &y);
add(x, y);
add(y, x);
}
dfs1(1);
dfs2(1, 1);
build(1, 1, n);
while(m--){
scanf("%d%d", &x, &y);
//更新结点x的权值为y
update(x, y);
//查询包含根节点的重链区间的广义矩阵乘积
matrix ans = query(1, 1, n, dfn[1], bot[1]);
//那么这个矩阵就包含了f[x][0]与f[x][1]
//g[0][0]==f[x][0]
//g[1][0]==f[x][1]
printf("%d\n", max(ans.g[0][0], ans.g[1][0]));
}
return 0;
}