Solution
看了简化版之后容易想到一个dp。
$dp_{u,0}$代表$u$的子树内不选$u$的最大答案。
$dp_{u,1}$代表$u$的子树内选$u$的最大答案。
有转移方程：
$dp_{u,0}=sum_{(u,v) in E} max(dp_{v,0}, dp_{v,1})$。
$dp_{u,1}=(sum_{(u,v) in E} dp_{v,0})+a_u$。
然后对于ddp的模板题我们就得到了一个$O(nm)$的优秀算法。
接下来我们就来看看怎么用ddp的套路来切掉这道题。
变成序列dp的形式
因为ddp只是利用树剖把树剖成一条条链，然后再链上做ddp，所以我们要有一个适应链dp的方程和状态。
我们在树剖时只能处理重边的结果，不能处理轻边的结果，所以我们要先把轻边的结果算出来。
设$u$的重儿子为$son(u)$。
因为是在重链上序列dp，所以我们要先把重儿子分离出来。
令$g_{u,0}=sum_{v e son(u)} max(dp_{v,1},dp_{v,0})$，$g_{u,1}=(sum_{v e son(u)} dp_{v,0}) + a_u$。
则有$dp_{u,0}=g_{u,0}+max(dp_{son(u),0}, dp_{son(u),1})$，$dp_{u,1}=g_{u,1}+dp_{son(u),0}$。
我们发现能做ddp还有一个前提是变成序列dp后可以用广义矩乘来表示转移，比如上面的例子可以表示成：
$left[ egin{matrix} g_{u,0} & g_{u,0} \ g_{u,1} & -inf end{matrix} ight] imes left[ egin{matrix} dp_{son(u),0} \ dp_{son(u),1} end{matrix} ight]=left[ egin{matrix} dp_{u,0} \ dp_{u,1} end{matrix} ight] $
然后我们就可以愉快的ddp了！要想查任意点的dp值只需查从它这个点到它所在的重链的结尾上的点的矩阵乘积即可（所以我们还需维护链尾），因为链尾的矩阵即为其dp值矩阵。
而这个$g$数组和$dp$数组都是可以在树链剖分时预处理出来的。
修改
我们发现我们只需修改$g$的值，即矩阵即可。
对于一个位置先把它的修改了，然后跳到它的链头的父亲，继续循环做直到到根。
为什么可以这么做因为$g$是与重链无关的，只用修改轻链的情况。
具体修改时需要记录前一个点（即前一条重链的联投）的dp值修改前后的增量，然后用之前的值加上其即可（因为是修改一个轻儿子）。
具体可看代码。
查询
查询时查根的dp值即可。
Code
#include <iostream> #include <cstdio> #include <cstring> using namespace std; const int N = 100010; //输入输出 template <typename T> void read(T &x) { int f = 1; char ch = getchar(); x = 0; for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1; for (; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0'; x *= f; } template <typename T> void write(T x) { if (x > 9) write(x / 10); putchar(x % 10 + '0'); } template <typename T> void print(T x) { if (x < 0) x = -x, putchar('-'); write(x); putchar(' '); } template <typename T> void cmax(T &x, T y) {if (y > x) x = y;} template <typename T> void cmin(T &x, T y) {if (y < x) x = y;} int n;//节点个数 int m;//操作个数 int a[N];//初始值 int dp[N][2];//dp数组 //前向星 namespace QXX{ struct node{ int pre, to; }edge[N << 1]; int head[N], tot; inline void add(int u, int v) {//加边 edge[++tot].pre = head[u]; edge[tot].to = v; head[u] = tot; } }using namespace QXX; //矩阵 namespace MATRIX{ struct Matrix{ int arr[3][3]; }A[N]; inline void init(Matrix &X) {memset(X.arr, 0xcf, sizeof(X.arr));} inline Matrix Mul(Matrix X, Matrix Y) { Matrix Z; init(Z); for (int i = 1; i <= 2; i++) for (int j = 1; j <= 2; j++) for (int k = 1; k <= 2; k++) cmax(Z.arr[i][j], X.arr[i][k] + Y.arr[k][j]); return Z; } }using namespace MATRIX; //树链剖分 namespace TCP{ int dfn[N], num;//dfs 序 int top[N];//链头 int End[N];//链尾 int pos[N];//pos[i] 代表 dfs 序为 i 的节点是哪个 int sz[N];//子树大小 int fa[N];//父亲 int son[N];//重儿子 void dfs1(int x) {//预处理子树大小、父亲和重儿子 sz[x] = 1; for (int i = head[x]; i; i = edge[i].pre) { if (fa[x] == edge[i].to) continue; fa[edge[i].to] = x; dfs1(edge[i].to); sz[x] += sz[edge[i].to]; if (sz[edge[i].to] > sz[son[x]]) son[x] = edge[i].to; } } void dfs2(int x, int chain) {//树链剖分预处理 dfn[x] = ++num, top[x] = chain, pos[num] = x; init(A[x]); A[x].arr[1][1] = A[x].arr[1][2] = 0; A[x].arr[2][1] = a[x]; if (son[x]) dfs2(son[x], chain), dp[x][0] = max(dp[son[x]][1], dp[son[x]][0]), dp[x][1] = dp[son[x]][0];//加上重链信息 else End[chain] = dfn[x]; for (int i = head[x]; i; i = edge[i].pre) {//处理轻儿子 if (edge[i].to == fa[x] || edge[i].to == son[x]) continue; dfs2(edge[i].to, edge[i].to); A[x].arr[1][1] += max(dp[edge[i].to][1], dp[edge[i].to][0]); A[x].arr[1][2] = A[x].arr[1][1]; A[x].arr[2][1] += dp[edge[i].to][0]; } dp[x][0] += A[x].arr[1][1]; dp[x][1] += A[x].arr[2][1]; } }using namespace TCP; namespace Segment_Tree{ struct Segment{ Matrix val; }tr[N << 2]; inline void push_up(int p) {tr[p].val = Mul(tr[p << 1].val, tr[p << 1 | 1].val);} void build(int p, int l, int r) { if (l == r) { tr[p].val = A[pos[l]]; return; } int mid = (l + r) >> 1; build(p << 1, l, mid); build(p << 1 | 1, mid + 1, r); push_up(p); } void change(int p, int l, int r, int Pos) { if (l == r) { tr[p].val = A[pos[l]]; return; } int mid = (l + r) >> 1; if (Pos <= mid) change(p << 1, l, mid, Pos); else change(p << 1 | 1, mid + 1, r, Pos); push_up(p); } Matrix query(int p, int l, int r, int L, int R) { if (L <= l && r <= R) { return tr[p].val; } int mid = (l + r) >> 1; if (R <= mid) return query(p << 1, l, mid, L, R); else if (L > mid) return query(p << 1 | 1, mid + 1, r, L, R); else return Mul(query(p << 1, l, mid, L, mid), query(p << 1 | 1, mid + 1, r, mid + 1, R)); } }using namespace Segment_Tree; int main() { read(n); read(m); for (int i = 1; i <= n; ++i) read(a[i]); for (int i = 1, u, v; i < n; ++i) { read(u); read(v); add(u, v); add(v, u); } dfs1(1); dfs2(1, 1); build(1, 1, n); while (m--) { int x, y; read(x); read(y); A[x].arr[2][1] += y - a[x]; a[x] = y; while (x != 0) { Matrix bef = query(1, 1, n, dfn[top[x]], End[top[x]]); change(1, 1, n, dfn[x]); Matrix aft = query(1, 1, n, dfn[top[x]], End[top[x]]); x = fa[top[x]]; A[x].arr[1][1] += max(aft.arr[1][1], aft.arr[2][1]) - max(bef.arr[1][1], bef.arr[2][1]); A[x].arr[1][2] = A[x].arr[1][1]; A[x].arr[2][1] += aft.arr[1][1] - bef.arr[1][1]; } Matrix ans = query(1, 1, n, top[1], End[top[1]]); print(max(ans.arr[1][1], ans.arr[2][1])); } return 0; }