题目地址：洛谷：【P4643】【模板】动态dp – 洛谷

题目描述

给定一棵 n 个点的树，点带点权。
有 m 次操作，每次操作给定 x, y ，表示修改点 x 的权值为 y 。
你需要在每次操作之后求出这棵树的最大权独立集的权值大小。

输入输出格式

输入格式：
第一行， n, m ，分别代表点数和操作数。
第二行， V1, V2, …, Vn ，代表 n 个点的权值。
接下来 n-1 行， x, y ，描述这棵树的 n-1 条边。
接下来 m 行， x, y ，修改点 x 的权值为 y 。

输出格式：
对于每个操作输出一行一个整数，代表这次操作后的树上最大权独立集。
保证答案在 int 范围内

输入输出样例

输入样例#1：

10 10
-11 80 -99 -76 56 38 92 -51 -34 47 
2 1
3 1
4 3
5 2
6 2
7 1
8 2
9 4
10 7
9 -44
2 -17
2 98
7 -58
8 48
3 99
8 -61
9 76
9 14
10 93

输出样例#1：

186
186
190
145
189
288
244
320
258
304

说明

对于30%的数据， 1≤n,m≤10
对于60%的数据， 1≤n,m≤1000
对于100%的数据， 1≤n,m≤10^5

题解

参考资料：Luogu P4643 【模板】动态dp – 胡小兔 – 博客园
首先这个题不带修改就是一个“没有上司的舞会”模型，用$dp[u][0/1]$代表$u$这个点选或不选其子树中的最大权独立集的权值和，DFS向上转移即可。
现在我们需要动态地维护树上的DP值，我们需要一种方法来使权值能快速更新。在这道题里，我们的转移方程是
$$ \begin{aligned}
dp[u][0] &= \sum_{v \text{ is a son of } u} \max \{ dp[v][0], dp[v][1] \} \\
dp[u][1] &= \sum_{v \text{ is a son of } u} dp[v][0]
\end{aligned} $$
首先不好搞的是儿子的数量比较多求和不好做，我们先考虑把树给剖掉，使用$g[u][0/1]$记录$u$这个点选或不选其自身和所有轻儿子的答案的和，而$f[u][0/1]$则记录总的答案，即合并轻重儿子考虑。现在，方程变成了这样
$$ \begin{aligned}
f[u][0] &= g[u][0] + \max \{ f[v][0], f[v][1] \} \\
f[u][1] &= g[u][1] + f[v][0]
\end{aligned} $$
其中的$v$是$u$的重儿子。到现在为止，似乎也没有把转移的形式变得可以树上操作，而且怎么求$g[u][0/1]$的值也不知道。这时，我们想到了矩阵。
矩阵的乘法可以理解为向量运算，即$\mathbf{A} \times \mathbf{B}$可以理解为$\mathbf{B}$中的每一个行向量$\mathbf{b_1}$乘上$\mathbf{A}$中每一行对应的系数$\{ a_{1, 1}, a_{1, 2}, \dots, a_{1, n} \}$再加起来得到的行向量组（或者也可以用列向量的形式理解）。
在这里，我们需要重新定义向量加法和标量乘法。
$$ \begin{aligned}
\mathbf{a} + \mathbf{b} = \mathbf{c} &\Rightarrow c_i = \max \{ a_i, b_i \} \\
\mathbf{a} \times b = \mathbf{c} &\Rightarrow c_i = a_i + b
\end{aligned} $$
我们发现上面的重新定义的运算具有很好的性质，可以按照这样的定义构造向量空间，来定义新的矩阵乘法。新的矩阵乘法如下
$$ \mathbf{A} \times \mathbf{B} = \mathbf{C} \Rightarrow C_{i, j} = \max_k \{ A_{i, k} + B_{k, j} \} $$
这样，我们就可以构造一个矩阵来进行DP的转移了
$$ \begin{bmatrix} f[u][0] \\ f[u][1] \end{bmatrix} = \begin{bmatrix} f[v][0] \\ f[v][1] \end{bmatrix} \times \begin{bmatrix} g[u][0] & g[u][0] \\ g[u][1] & 0 \end{bmatrix} $$
那么，只要我们知道了整棵树上的转移矩阵（即右侧的那个$2 \times 2$矩阵），就可以通过线段树维护重链矩阵乘法，从而快速求某条重链顶端的答案了。我们无需设置一个列向量来乘上这个转移矩阵，这是因为，叶子节点的$f[u][0]=g[u][0]=0, f[u][1]=g[u][1]=w_u$，看上去就跟列向量一样了。
接下来考虑修改问题，我们考虑更新这个结点的矩阵后，沿重链上跳，每个重点的顶的父亲都会受到影响，此时只需要把影响大力算出来改一下就好。
我的初始化是逐个点改权值，复杂度是$O(n \log^2 n)$的，实际上可以先$O(n)$地做一遍DP，然后用DP值构造矩阵，这个复杂度是$O(n+n \log n)$，相比而言常数更优秀，不过代码更长，考虑到这个题没卡常，就懒得写了233
总复杂度是$O((n+m) \log^2 n)$。

代码

// Code by KSkun, 2018/7
#include <cstdio>
#include <cctype>
#include <cstring>

#include <algorithm>
#include <vector>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
        ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1; register char c = fgc();
    for(; !isdigit(c); c = fgc()) if(c == '-') neg = -1;
    for(; isdigit(c); c = fgc()) res = (res << 1) + (res << 3) + c - '0';
    return res * neg;
}

const int MAXN = 100005;

struct Matrix {
    LL m[2][2];
    Matrix() {
        memset(m, 0, sizeof(m));
    }
    inline LL* operator[](const int &x) const {
        return const_cast<LL*>(m[x]);
    }
    inline Matrix operator*(const Matrix &rhs) const {
        Matrix res;
        for(int i = 0; i <= 1; i++) {
            for(int j = 0; j <= 1; j++) {
                for(int k = 0; k <= 1; k++) {
                    res[i][j] = std::max(res[i][j], m[i][k] + rhs[k][j]);
                }
            }
        }
        return res;
    }
    inline Matrix& operator*=(Matrix &rhs) {
        return *this = *this * rhs;
    }
};

int n, m, w[MAXN];
std::vector<int> gra[MAXN];

int fa[MAXN], siz[MAXN], dep[MAXN], son[MAXN], top[MAXN], end[MAXN], dfn[MAXN], vn[MAXN], clk;

void dfs1(int u) {
    siz[u] = 1;
    for(auto v : gra[u]) {
        if(v == fa[u]) continue;
        fa[v] = u; dep[v] = dep[u] + 1;
        dfs1(v);
        if(siz[v] > siz[son[u]]) son[u] = v;
    }
}

void dfs2(int u, int tp) {
    dfn[u] = ++clk; vn[dfn[u]] = u; top[u] = tp; 
    end[tp] = std::max(end[tp], dfn[u]);
    if(son[u]) {
        dfs2(son[u], tp);
    }
    for(auto v : gra[u]) {
        if(v == fa[u] || v == son[u]) continue;
        dfs2(v, v);
    }
}

Matrix tr[MAXN << 2], val[MAXN];

#define lch o << 1
#define rch o << 1 | 1
#define mid ((l + r) >> 1)

void modify(int o, int l, int r, int x) {
    if(l == r) {
        tr[o] = val[vn[l]]; return;
    }
    if(x <= mid) modify(lch, l, mid, x);
    else modify(rch, mid + 1, r, x);
    tr[o] = tr[lch] * tr[rch];
}

Matrix query(int o, int l, int r, int ll, int rr) {
    if(l == ll && r == rr) return tr[o];
    if(rr <= mid) return query(lch, l, mid, ll, rr);
    else if(ll > mid) return query(rch, mid + 1, r, ll, rr);
    else return query(lch, l, mid, ll, mid) * query(rch, mid + 1, r, mid + 1, rr);
}

inline Matrix query(int u) {
    return query(1, 1, n, dfn[top[u]], end[top[u]]);
}

inline void modify(int u, int v) {
    val[u][1][0] += v - w[u];
    w[u] = v;
    Matrix m1, m2;
    while(u) {
        m1 = query(top[u]);
        modify(1, 1, n, dfn[u]);
        m2 = query(top[u]);
        u = fa[top[u]];
        val[u][0][0] += std::max(m2[0][0], m2[1][0]) - std::max(m1[0][0], m1[1][0]);
        val[u][0][1] = val[u][0][0];
        val[u][1][0] += m2[0][0] - m1[0][0];
    }
}

int main() {
    n = readint(); m = readint();
    for(int i = 1; i <= n; i++) {
        w[i] = readint();
    }
    for(int i = 1, u, v; i < n; i++) {
        u = readint(); v = readint();
        gra[u].push_back(v); gra[v].push_back(u);
    }
    dfs1(1);
    dfs2(1, 1);
    for(int i = 1; i <= n; i++) {
        int t = w[i]; w[i] = 0;
        modify(i, t);
    }
    while(m--) {
        int x = readint(), y = readint();
        modify(x, y);
        Matrix res = query(1);
        printf("%lld\n", std::max(res[0][0], res[1][0]));
    }
    return 0;
}