[洛谷4643]【模板】动态dp 题解
![[洛谷4643]【模板】动态dp 题解](https://ksmeow.moe/wp-content/uploads/2018/07/180710a.jpg)
题目地址：洛谷：【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;
}
