可能更好的阅读体验

P4719 【模板】动态 DP - 洛谷

动态 dp？新东西，猫娘学习。

希望我贫瘠的线性代数知识能帮到你。

动态树最大权独立集（支持单点修改）

问题描述

有 $m$ 次操作，每次操作给定 $x, y$，表示修改点 $x$ 的权值为 $y$。
每次操作后，需要求出整棵树的最大权独立集的权值大小。

---

静态 DP 回顾

不考虑修改时，这是经典的树上最大权独立集问题（"没有上司的晚会"）。

定义：

• $dp_{u,0}$：以 $u$ 为根的子树中，不选 $u$ 时的最大权值。
• $dp_{u,1}$：以 $u$ 为根的子树中，选 $u$ 时的最大权值。

转移方程：

$$dp_{u,0} = \sum_{v \in children(u)} \max(dp_{v,0}, dp_{v,1})$$$$dp_{u,1} = V_u + \sum_{v \in children(u)} dp_{v,0}$$

答案为：

$$\max(dp_{root,0}, dp_{root,1})$$

---

动态修改的挑战

每次修改单个点权，若重新跑整棵树 DP，复杂度为 $O(n)$，无法应对大数据。

---

解决方案：轻重链剖分 + 矩阵维护

核心思想

• 对树进行轻重链剖分。
• 将每个节点的 DP 转移表示为线性变换（矩阵）。
• 每条重链上的 DP 用线段树维护矩阵乘积。
• 修改点时，只更新该点到根路径上涉及的重链（跳链更新）。

---

1. 矩阵表示

向量表示

将节点 $u$ 的 DP 值写作向量：

$$\begin{bmatrix} dp_{u,0} \\ dp_{u,1} \end{bmatrix}$$

---

轻儿子贡献预处理

定义：

• $g_{u,0} = \sum_{v \in light\_children(u)} \max(dp_{v,0}, dp_{v,1})$
• $g_{u,1} = V_u + \sum_{v \in light\_children(u)} dp_{v,0}$

其中"轻儿子"指除重儿子外的所有儿子。

---

重儿子转移

设重儿子为 $son$，则：

$$\begin{bmatrix} dp_{u,0} \\ dp_{u,1} \end{bmatrix} = \begin{bmatrix} \max(dp_{son,0}, dp_{son,1}) + g_{u,0} \\ dp_{son,0} + g_{u,1} \end{bmatrix}$$

由于 $\max$ 不是线性运算，引入 max-plus 广义矩阵乘法。

---

Max-Plus 矩阵乘法定义

定义运算 $\otimes$：

$$C_{i,j} = \max_k (A_{i,k} + B_{k,j})$$

这样 $\max$ 可以纳入矩阵运算。

---

构造转移矩阵

我们希望：

$$\begin{bmatrix} dp_{u,0} \\ dp_{u,1} \end{bmatrix} = M_u \otimes \begin{bmatrix} dp_{son,0} \\ dp_{son,1} \end{bmatrix}$$

其中：

$$M_u = \begin{bmatrix} g_{u,0} & g_{u,0} \\ g_{u,1} & -\infty \end{bmatrix}$$

解释：

• 第一行第一列：$g_{u,0} + dp_{son,0}$
• 第一行第二列：$g_{u,0} + dp_{son,1}$
• 第二行第一列：$g_{u,1} + dp_{son,0}$
• 第二行第二列：$-\infty$（不能选重儿子时再选 $u$）

因此：

$$dp_{u,0} = \max(g_{u,0} + dp_{son,0},\; g_{u,0} + dp_{son,1}) = g_{u,0} + \max(dp_{son,0}, dp_{son,1})$$$$dp_{u,1} = g_{u,1} + dp_{son,0}$$

---

怕有人还是不太懂矩阵乘法，我再解释下：

$M_u$ 中第一行第一列的 $g_{u,0}$ 配上第一行第一列的 $dp_{son,0}$，可以贡献第一行第一列的 $dp_{u,0}$。
$M_u$ 中第一行第二列的 $g_{u,0}$ 配上第二行第一列的 $dp_{son,1}$，可以贡献第一行第一列的 $dp_{u,0}$。
$M_u$ 中第二行第一列的 $g_{u,0}$ 配上第一行第一列的 $dp_{son,0}$，可以贡献第二行第一列的 $dp_{u,1}$。
$M_u$ 中第二行第二列的 $-\infty$ 配上第二行第一列的 $dp_{son,1}$，可以贡献第二行第一列的 $dp_{u,0}$。

---

2. 重链内维护

• 每条重链分配一个线段树。
• 线段树维护该重链上节点矩阵的乘积（按深度从浅到深顺序）。
• 叶子节点（无重儿子）视为重儿子不存在，其矩阵仍按定义构造。

---

修改流程

当修改点 $x$ 的权值为 $y$ 时：

1. 更新 $x$ 的矩阵
   修改 $V_x$，从而更新 $g_{x,1}$。

2. 沿重链向上更新
   对当前节点 $u$：

   • 更新其所在重链的线段树，得到该链顶端节点的新 DP 向量。
   • 若链顶为 $top$，则 $top$ 的父节点 $fa$ 的轻儿子贡献发生变化，需更新 $g_{fa,0}$ 或 $g_{fa,1}$。
   • 然后继续处理 $fa$ 所在的重链，直到根节点。

---

复杂度分析

• 每次修改涉及的重链数量为 $O(\log n)$。
• 每条重链上的线段树更新为 $O(\log n)$。
• 总复杂度：$O(\log^2 n)$。

---

3. 代码实现

#include<bits/stdc++.h>
using namespace std;
 
const int N = 1e5 + 10;
const int inf = 0x3f3f3f3f;
 
#define lc(p) (p << 1)
#define rc(p) ((p << 1) | 1)
#define mid ((l + r) >> 1)
 
int n, m;          
int a[N];         
vector<int> G[N];  
 
int fa[N], siz[N], son[N]; // 父亲、子树大小、重儿子
int f[N][2];               // 静态DP：f[x][0/1] 表示x不选/选时的子树最大权
int dfn[N], id[N], top[N], bot[N], tsp;
// dfn[x]：节点 x 的 dfs 序（时间戳），id[t]：dfs序 t 对应的节点编号
// top[x]：x 所在重链的链头节点，bot[top]：链头 top 所在链的链尾节点的 dfs 序（即链的区间右端点）
// tsp：dfs 序计数器
 
// 第一次 DFS：处理 fa, siz, son，并计算静态 DP 初值
void dfs(int x) {
    siz[x] = 1;
    f[x][1] = a[x];      // 选 x，初始贡献为自己的权值
 
    for (int y : G[x]) if (fa[x] != y) {
        fa[y] = x;
        dfs(y);
        siz[x] += siz[y];
 
        if (siz[y] > siz[son[x]]) {
            son[x] = y; // 更新重儿子
        }
 
        // 正常树上 DP 转移
        f[x][0] += max(f[y][0], f[y][1]);      // x 不选，儿子可选可不选
        f[x][1] += f[y][0];                    // x 选，儿子必须不选
    }
}
 
// 第二次 DFS：树链剖分，分配 dfs 序，确定 top 和 bot
void dfs(int x, int tp) {
    dfn[x] = ++ tsp;
    id[tsp] = x;
 
    top[x] = tp;
    bot[tp] = tsp;       // 更新链尾的 dfn（因为 dfs 序连续，最后遍历到的就是链尾）
 
    if (son[x]) {
        dfs(son[x], tp); // 优先重儿子，保持链上dfs序连续
    }
    for (int y : G[x]) if (y != fa[x] && y != son[x]) {
        dfs(y, y);                // 轻儿子开新链
    }
}
 
// ---------- 矩阵结构体：用于动态DP的转移矩阵 ----------
struct Matrix {
    int g[2][2];
    // 重载乘法：广义矩阵乘法（max-plus）
    Matrix operator*(Matrix b) {
        Matrix t;
        memset(t.g, -0x3f, sizeof(t.g));
 
        for (int i = 0; i <= 1; i ++)
            for (int j = 0; j <= 1; j ++)
                for (int k = 0; k <= 1; k ++)
                    t.g[i][j] = max(t.g[i][j], g[i][k] + b.g[k][j]);
        return t;
    }
} mt[N], tr[N << 2];
// mt[x]：节点x的转移矩阵（仅考虑轻儿子贡献）
// tr[p]：线段树节点，维护一段 dfs 序区间的矩阵乘积
 
void pushup(int p) {
    tr[p] = tr[lc(p)] * tr[rc(p)];
}
 
void build(int p, int l, int r) {
    if (l == r) {
        int x = id[l];            // 当前dfs序对应的节点
        int g0 = 0, g1 = a[x];    // g0: x 不选，g1: x 选
        // 遍历轻儿子（非重儿子、非父亲），累加其DP值
        for (auto y : G[x]) {
            if (y != fa[x] && y != son[x]) {
                g0 += max(f[y][0], f[y][1]);  // x 不选时，轻儿子任意
                g1 += f[y][0];                // x 选时，轻儿子不选
            }
        }
        // 构造转移矩阵：
        // g[0][0] = g[0][1] = g0 （不选 x 时，当前链状态任意，下一状态也是不选）
        // g[1][0] = g1          （选 x，下一状态必须不选）
        // g[1][1] = -inf        （选 x 后不能转移到选，因为相邻不能同时选）
        tr[p] = mt[x] = {g0, g0, g1, -inf};
        return ;
    }
    build(lc(p), l, mid);
    build(rc(p), mid + 1, r);
    pushup(p);
}
 
// 线段树单点更新
void change(int p, int l, int r, int x) {
    if (x < l || r < x) {
        return ;
    }
    if (l == r) {
        tr[p] = mt[id[l]];
        return;
    }
    change(lc(p), l, mid, x);
    change(rc(p), mid + 1, r, x);
    pushup(p);
}
 
// 线段树区间查询：返回区间 [x, y] 的矩阵乘积
Matrix query(int p, int l, int r, int x, int y) {
    if (x == l && r == y) {    // 必须刚刚好
        return tr[p];
    }
    if (y <= mid) return query(lc(p), l, mid, x, y);
    if (x > mid) return query(rc(p), mid + 1, r, x, y);
    // 跨区间，先左后右，注意乘法顺序（左乘右）
    return query(lc(p), l, mid, x, mid) * query(rc(p), mid + 1, r, mid + 1, y);
}
 
// 动态 DP 核心：修改点权并更新所有影响
void update(int u, int k) {
    // 更新点 u 的转移矩阵中关于 “选 u” 的项（轻儿子贡献不变，只变自身权值）
    mt[u].g[1][0] += k - a[u];
    a[u] = k;                // 更新权值
 
    // 从 u 开始，沿重链向上更新，直到根
    while (u) {
        // 先查询当前 u 所在链的旧矩阵乘积（整条链的转移）
        Matrix old = query(1, 1, n, dfn[top[u]], bot[top[u]]);
 
        // 将 u 的叶子节点在线段树中更新（此时 mt[u] 已变）
        change(1, 1, n, dfn[u]);
 
        // 查询更新后该链的新矩阵乘积
        Matrix now = query(1, 1, n, dfn[top[u]], bot[top[u]]);
 
        // 当前链的矩阵变化会影响其父链：当前链头作为父节点的一个轻儿子，
        // 因此需要更新父节点（即链头 top[u] 的父亲）的轻儿子贡献。
        u = fa[top[u]];          // 跳转到父链的节点（即当前链头的父亲）
        if (!u) break;          // 到达根的上方，结束
 
        // 根据新旧链矩阵的DP结果差值，更新父节点u的轻儿子贡献
        // old 和 now 的 g[0][0] 和 g[1][0] 分别代表该链头节点不选/选时的最大权
        // 父节点 u 不选时，轻儿子可任意
        // 所以要加上 max(now.g[0][0], now.g[1][0]) - max(old.g[0][0], old.g[1][0])
 
        mt[u].g[0][0] += max(now.g[0][0], now.g[1][0]) - max(old.g[0][0], old.g[1][0]);
        mt[u].g[0][1] = mt[u].g[0][0];   // g[0][0] 和 g[0][1] 相同，因为不选时下一状态任意
 
 
        // 父节点 u 选时，该轻儿子必须不选，所以变化量为 now.g[0][0] - old.g[0][0]
        mt[u].g[1][0] += now.g[0][0] - old.g[0][0];
        // 注意：mt[u].g[1][1] 始终为 -inf，保持不变
    }
}
 
int 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 x, y;
        cin >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
 
    fa[1] = 0; tsp = 0;
    memset(son, 0, sizeof(son));
    dfs(1);            // 第一次 DFS：求 fa, size, son, 静态 DP
    dfs(1, 1);        // 第二次 DFS：树链剖分，分配 dfn
    build(1, 1, n);
 
    while (m --) {
        int x, y;
        cin >> x >> y;
        update(x, y); 
 
        Matrix ans = query(1, 1, n, dfn[1], bot[1]);  // 查询整棵树（根 1 所在链）的矩阵
        cout << max(ans.g[0][0], ans.g[1][0]) << "\n"; 
    }
    return 0;
}