我的博客：可能更好的阅读体验

不是本猫娘说，学个动态 DP 还得学 LCT？

本文默认你学过线段树版本的动态 DP。

线段树版本 oj 内链

#include <bits/stdc++.h>
using namespace std;
 
#define int long long     // 最方便 
const int N = 1e6 + 10;
const int inf = 0x3f3f3f3f;
 
int n, m;
int a[N];
vector<int> G[N];
 
int fa[N], siz[N], son[N];   // 原树父亲、子树大小、重儿子
int f[N][2];                 // 考虑节点 x 不选 / 选 的 DP 贡献值
 
// 和线段树不同的是，我们新建了 g 数组来辅助处理
// 实际逻辑和线段树版本是一样的，g 数组不起任何实际作用，只帮助理解 
int g[N][2];  // 只考虑节点 x 的所有轻儿子（不包括重儿子）时 x 不选/选的 DP 贡献值
int gfa[N];        // GBBT 中的父亲
int ls[N], rs[N];  // GBBT 左右儿子
 
struct Matrix {
    int g[2][2];
    Matrix() { 
        memset(g, -0x3f, sizeof(g)); 
    }
    
    void change(int g0, int g1) {
        g[0][0] = g[0][1] = g0;
        g[1][0] = g1;
        g[1][1] = -inf;
    }
    
    Matrix operator * (const Matrix &b) const {
        Matrix c;
        for (int i = 0; i < 2; i ++)
            for (int j = 0; j < 2; j ++)
                for (int k = 0; k < 2; k ++)
                    c.g[i][j] = max(c.g[i][j], g[i][k] + b.g[k][j]);
        return c;
    }
} mt[N], tr[N];
 
 
// 第一次 DFS：求 fa, siz, son, 静态 DP
void dfs(int x) {
    siz[x] = 1;
    f[x][1] = a[x];
    g[x][0] = 0;        // 初始化轻儿子贡献
    g[x][1] = a[x];
    
    for (int y : G[x]) if (y != fa[x]) {
        fa[y] = x;
        dfs(y);
        siz[x] += siz[y];
        if (siz[y] > siz[son[x]]) {
			son[x] = y;
		}
        
        f[x][0] += max(f[y][0], f[y][1]);
        f[x][1] += f[y][0];
    }
}
 
 
int b[N], bs[N];   
// b[]：重链节点序列（按深度从小到大），bs[]：顺着重链权值前缀和
 
// GBBT 重链内处理 
// 传参：当前处理的重链节点序列区间 [l, r]
// 返回值：构建出的子树的根节点编号
int g_build(int l, int r) {
    // 递归边界：区间只有一个节点，直接作为叶子返回
    if (l == r) {
        tr[b[l]] = mt[b[l]];  // 该节点的矩阵就是它自己的转移矩阵
        return b[l];
    }
    
    // 二分寻找带权中点
    int L = l, R = r, pm = l;    
    int len = bs[r] - bs[l - 1];    // len：当前区间所有节点的权值总和
    
    // 二分查找带权中点：让左半部分的权值和尽量接近总权值的一半
    // 这样能保证左右子树平衡，路径长度 O(log n)
    while (L < R) {
        int mid = (L + R) >> 1;
        // 检查 [l, mid] 区间的权值和是否 ≤ 总权值的一半
        if ((bs[mid] - bs[l - 1]) * 2 <= len) {
            L = mid + 1;   // 可以继续右移，让左半更大
            pm = mid;
        }
        else { 
            R = mid - 1; // 左半太大，需要左移
        }
    }
    
    // 以带权中点 pm 作为根节点
    int rt = b[pm];          // 取出中点对应的节点编号作为根
    tr[rt] = mt[rt];        // 初始矩阵为当前节点的转移矩阵
    
    // 递归构建左右子树
    // 构建左子树：[l, pm - 1]（深度更浅的节点）
    if (l <= pm - 1) {
        ls[rt] = g_build(l, pm - 1);    // 递归构建，左儿子指向子树根
        gfa[ls[rt]] = rt;              // 设置左儿子在 GBBT 中的父亲为 rt
        
        tr[rt] = tr[ls[rt]] * tr[rt];
		// 矩阵乘法顺序：左子树（浅层）× 当前节点
        // 因为中序遍历是从浅到深，所以左子树在前
    }
    
    // 构建右子树：[pm + 1, r]（深度更深的节点）
    if (r >= pm + 1) {
        rs[rt] = g_build(pm + 1, r);    // 递归构建，右儿子指向子树根
        gfa[rs[rt]] = rt;              // 设置右儿子在 GBBT 中的父亲为 rt
        
        tr[rt] = tr[rt] * tr[rs[rt]];
		// 矩阵乘法顺序：当前节点 × 右子树（深层）
        // 中序遍历顺序：左 -> 中 -> 右，所以右子树在后
    }
    
    return rt;  // 返回当前子树的根节点
}
 
 
// 处理整棵树轻链间的连接，和重链节点序列和前缀和 
int build(int u) {
    int v = u, tp = 0;
    
    // 处理所有轻子树，并计算当前节点的轻儿子贡献（使用静态 f）
    while (v) {
        int g0 = 0, g1 = a[v];    // g0 不选 v，g1 强制选 v 
        for (int y : G[v]) {
            if (y != fa[v] && y != son[v]) {
                g0 += max(f[y][0], f[y][1]);
                g1 += f[y][0];
            }
        }
        g[v][0] = g0;
        g[v][1] = g1;
        mt[v].change(g0, g1);
        
        // 递归构建轻子树的 GBBT，并通过 gfa 连接到 v
        for (int y : G[v]) {
            if (y != fa[v] && y != son[v]) {
                int lcrt = build(y);
                gfa[lcrt] = v;
            }
        }
        v = son[v];   // 下一个重儿子 
    }
    
    // 收集当前重链节点
    while (u) {
        b[++ tp] = u;
        bs[tp] = bs[tp - 1] + siz[u] - siz[son[u]];
        u = son[u];
    }
    
    int RT = g_build(1, tp);   // 有完整重链后处理 
    return RT;
}
 
// 判断节点 x 是否通过轻边连接到父亲，是 1，不是 0 
// 在 GBBT 中，每个节点都有 gfa[x] 指向它的父节点
// 可能是同一条重链内的父亲，也可能是轻边连接的父链
// 但只有和父亲在同一条重链上，才会是父亲的左 / 右子节点 
inline bool isLight(int u) {
    return gfa[u] && ls[gfa[u]] != u && rs[gfa[u]] != u;
}
 
// 动态 DP 更新
void update(int u, int k) {
    g[u][1] += k - a[u];
    a[u] = k;  
    mt[u].change(g[u][0], g[u][1]);
    
    // 沿 GBBT 向上更新
    while (u) {
        Matrix old = tr[u];
        
        // 重新计算当前节点的矩阵
        // 当前节点的矩阵 = 左儿子矩阵 × 当前节点val × 右儿子矩阵
        tr[u] = mt[u];                 
        if (ls[u]) tr[u] = tr[ls[u]] * tr[u];
        if (rs[u]) tr[u] = tr[u] * tr[rs[u]]; 
        
        // 处理轻边更新
        // 如果 u 是通过轻边连接到父节点的（即 u 是一条重链的根）
        // 那么 u 这棵子树的 DP 值发生了变化，需要更新父节点的 g 值
        if (isLight(u)) {
            // 计算 u 子树在 不选 / 选根节点 时的最大权值（即整条重链的 DP 结果）
            // 注意：old 和 tr 中的 g[0][0] 表示子树根不选时的最大权
            //                    g[1][0] 表示子树根选时的最大权
            int oldAns = max(old.g[0][0], old.g[1][0]);  // 更新前的整棵子树 DP 值
            int newAns = max(tr[u].g[0][0], tr[u].g[1][0]);  // 更新后的整棵子树 DP 值
            
            // 更新父节点的 g[0]（父节点不选时，这个轻儿子可任意）
            // 父节点不选时，轻儿子贡献增加：newAns - oldAns
            g[gfa[u]][0] += newAns - oldAns;
            
            // 更新父节点的 g[1]（父节点选时，这个轻儿子必须不选）
            // 父节点选时，轻儿子必须不选，所以只取 g[0][0]（根节点不选的情况）
            g[gfa[u]][1] += tr[u].g[0][0] - old.g[0][0];
            
            // 因为父节点的g值变了，需要重新构造父节点的转移矩阵
            mt[gfa[u]].change(g[gfa[u]][0], g[gfa[u]][1]);
        }
        
        // 继续向上跳，到 GBBT 中的父节点
        u = gfa[u];
    }
}
 
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 1; i < n; ++i) {
        int u, v;
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
     
    dfs(1);    // 第一次 DFS：求 fa, siz, son, 静态 DP
    int root = build(1);
    
    int last = -1;
    while (m--) {
        int x, y;
        cin >> x >> y;
        if (last != -1) {   // 洛谷模版题要求强制在线异或
            x ^= last;
        }
 
        update(x, y);
        int ans = max(tr[root].g[0][0], tr[root].g[1][0]);
        cout << ans << '\n';
        last = ans;
    }
    return 0;
}

C73【模板】动态DP+树剖+矩阵乘+线段树 P4719 动态树分治 C73blog

C76【模板】动态DP+LCT P4719 动态树分治 C76blog

// 动态DP+LCT O(nlogn)
#include<bits/stdc++.h>
using namespace std;
 
#define lc(x) ch[x][0]
#define rc(x) ch[x][1]
#define notroot(x) lc(fa[x])==x||rc(fa[x])==x
const int N=1000010,inf=(1<<30);
int n,m,a[N],f[N][2];
vector<int>G[N];
int ch[N][2],fa[N]; //splay:ch儿,fa父
struct matrix{
  int g[2][2];
  matrix(){g[0][0]=g[0][1]=g[1][0]=g[1][1]=-inf;}
  matrix operator*(matrix b){
    matrix t;
    for(int i=0;i<2;++i)
    for(int j=0;j<2;++j)
    for(int k=0;k<2;++k)
      t.g[i][j]=max(t.g[i][j],g[i][k]+b.g[k][j]);
    return t;
  }
}mt[N],tr[N]; //mt:节点x的g矩阵, tr:节点x的矩阵积
 
void dfs(int x){ //预处理fa,f,mt,tr
  f[x][1]=a[x];
  for(int y:G[x]){
    if(y!=fa[x]){
      fa[y]=x;
      dfs(y);
      f[x][0]+=max(f[y][0],f[y][1]);
      f[x][1]+=f[y][0];
    }
  }
  mt[x].g[0][0]=mt[x].g[0][1]=f[x][0];
  mt[x].g[1][0]=f[x][1];
  tr[x]=mt[x]; //初始时每个点就是一个splay
}
void pushup(int x){ //上传
  tr[x]=mt[x];
  if(lc(x))tr[x]=tr[lc(x)]*tr[x];
  if(rc(x))tr[x]=tr[x]*tr[rc(x)]; //矩阵积(即和取最大)
}
void rotate(int x){ //旋转x
  int y=fa[x],z=fa[y],k=rc(y)==x; //y的右儿是x吗
  if(notroot(y)) ch[z][rc(z)==y]=x; fa[x]=z; //z的儿是x,x的父是z
  ch[y][k]=ch[x][k^1]; fa[ch[x][k^1]]=y; //y的儿是x的异儿,x的异儿的父是y
  ch[x][k^1]=y; fa[y]=x; //x的异儿是y,y的父是x
  pushup(y); pushup(x);  //自底向上pushup
}
void splay(int x){ //x伸展到根
  while(notroot(x)){ //折线转xx,直线转yx
    int y=fa[x],z=fa[y];
    if(notroot(y)) (rc(y)==x)^(rc(z)==y)?rotate(x):rotate(y);
    rotate(x);
  }
}
void access(int x){ //打通x到树根的路
  for(int y=0; x;){
    splay(x);  //x转到当前splay的根
    if(rc(x)){ //x右儿子即将变成虚儿子,加上其贡献
      mt[x].g[0][0]+=max(tr[rc(x)].g[0][0],tr[rc(x)].g[1][0]);
      mt[x].g[1][0]+=tr[rc(x)].g[0][0];
      mt[x].g[0][1]=mt[x].g[0][0];
    }
    if(y){    //y即将变成x的实儿子,减去其贡献
      mt[x].g[0][0]-=max(tr[y].g[0][0],tr[y].g[1][0]);
      mt[x].g[1][0]-=tr[y].g[0][0];
      mt[x].g[0][1]=mt[x].g[0][0];
    }
    rc(x)=y;   //把y变成x的右儿子(即x指向下面splay的根)
    pushup(x); //更新x
    x=fa[y=x]; //把x存于y,x继续爬到上面的splay
  }
}
void update(int x,int y){ //修改点权
  access(x); //通路
  splay(x);  //伸展
  mt[x].g[1][0]+=y-a[x]; //修改x点
  pushup(x); a[x]=y;
}
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);
    G[x].push_back(y); G[y].push_back(x);
  }
  dfs(1); //预处理fa,f,mt,tr
  while(m--){
    scanf("%d%d",&x,&y);
    update(x,y);
    printf("%d\n",max(tr[x].g[0][0],tr[x].g[1][0]));
  } 
}