动态 DP 学习笔记
Visits: 451
动态 DP 在 NOIP2018D2T3 考察后风靡 OI 圈，然而我却一直没学。
引入
考虑这样一个问题：
给定一棵 $n$ 个点的树，点有点权 $w_i$。
有 $m$ 次操作，每次操作给定 $x,y$，表示将 $w_x$ 修改为 $y$。
每次操作后，询问这棵树的最大权独立集的权值大小。
$n,m \le 10^5$。
如果只有一次询问，我们显然可以用这样一个简单地树形 dp 解决：
设根为 $rt$。
设 $f_{i,0/1}$ 表示 $i$ 点不选/选时，$i$ 的子树内的最大答案。
转移为：
$$
\begin{cases}f_{x,0} = \sum_{y \in son_x} \max(f_{y,0}, f_{y,1}) \\f_{x,1} = w_x + \sum_{y \in son_x} f_{y,0}\end{cases}
$$目标为 $\max(f_{rt,0}, f_{rt,1})$。
多次询问呢？
这时候就需要可以解决树上带修 DP 问题的算法，也就是动态 DP。
动态 DP
广义矩阵乘法
定义广义矩阵乘法 $A \times B = C$ 为：
$$
C_{i,j} = \max_{k=1}^{n}(A_{i,k} + B_{k,j})
$$
即，将普通矩阵乘法中的乘法变成加法，加法变成取 $\max$。
同时，广义矩阵乘法满足结合律，所以可以使用矩阵快速幂。
动态 DP
首先进行树链剖分，设 $h_i$ 表示 $i$ 的重儿子。
设 $g_{i,0/1}$ 表示不选择/选择 $i$，同时只选择 $i$ 的轻儿子所在的子树的最大答案。
则有转移：
$$
\begin{cases}g_{x,0} = \sum_{y \in son_x, y \ne h_i} \max(f_{y,0}, f_{y,1}) \\g_{x,1} = w_x + \sum_{y \in son_x, y \ne h_i} f_{y,0} \\f_{x,0} = g_{x,0} + \max(f_{h_x, 0}, f_{h_x, 1}) \\f_{x,1} = g_{x,1} + f_{h_x,0}\end{cases}
$$
目标同样为 $\max(f_{rt,0}, f_{rt,1})$。
注意，这个转移是先计算 $g$ 后计算 $f$ 的，因此我们需要先处理轻儿子，然后处理重儿子。
考虑用线段树维护每条链的 dp 值，这样我们就可以单次 $\mathcal O(\log^2 n)$ 修改并回答询问了。
如何维护呢？
观察 $f$ 的转移，可以发现它等价于广义矩阵乘法的转移形式：
$$
\begin{bmatrix}g_{i,0} & g_{i,0}\\g_{i,1} & -\infty\end{bmatrix}\times \begin{bmatrix}f_{h_i,0} & 0\\f_{h_i,1} & 0\end{bmatrix}=\begin{bmatrix}f_{i,0} & 0\\f_{i,1}& 0\end{bmatrix}
$$
因此，对于每个点，我们维护矩阵 $\begin{bmatrix}g_{i,0} & g_{i,0}\\g_{i,1} & -\infty\end{bmatrix}$，则一条链的链顶的 $\begin{bmatrix}f_{i,0} & 0\\f_{i,1}& 0\end{bmatrix}$，就等于这条链上的矩阵从上到下相乘后的矩阵。
于是，我们用线段树维护矩阵 $\begin{bmatrix}g_{i,0} & g_{i,0}\\g_{i,1} & -\infty\end{bmatrix}$ 的连乘积就可以了。
【模板】P4719 【模板】动态 DP
const int N = 1e5 + 7, inf = 1e9;
int n, m, w[N], d[N], f[N], s[N], son[N];
int dfn[N], rnk[N], top[N], pot[N], num, F[N][2], G[N][2];
vi e[N];
struct mat {
int a[2][2];
inline mat() { memset(a, 0, sizeof(a)); }
inline friend mat operator * (mat a, mat b) {
mat c;
for (int i = 0; i < 2; i++)
for (int j = 0; j < 2; j++)
for (int k = 0; k < 2; k++)
c.a[i][j] = max(c.a[i][j], a.a[i][k] + b.a[k][j]);
return c;
}
} g[N];
struct T {
int l, r;
mat a;
} t[N<<2];
void dfs(int x) {
s[x] = 1, F[x][1] = w[x];
for (int y : e[x])
if (y != f[x]) {
f[y] = x, d[y] = d[x] + 1;
dfs(y), s[x] += s[y];
if (s[y] > s[son[x]]) son[x] = y;
F[x][0] += max(F[y][0], F[y][1]);
F[x][1] += F[y][0];
}
}
void dfs(int x, int p) {
dfn[x] = ++num, rnk[num] = x;
top[x] = p, pot[p] = x;
G[x][1] = w[x];
if (son[x]) dfs(son[x], p);
for (int y : e[x])
if (y != f[x] && y != son[x]) {
dfs(y, y);
G[x][0] += max(F[y][0], F[y][1]);
G[x][1] += F[y][0];
}
}
void build(int p, int l, int r) {
t[p].l = l, t[p].r = r;
if (l == r) return t[p].a = g[rnk[l]], void();
build(ls, l, md), build(rs, md + 1, r);
t[p].a = t[ls].a * t[rs].a;
}
void mdf(int p, int x) {
if (t[p].l == t[p].r) return t[p].a = g[rnk[x]], void();
mdf(x <= md ? ls : rs, x);
t[p].a = t[ls].a * t[rs].a;
}
mat ask(int p, int l, int r) {
if (t[p].l >= l && t[p].r <= r) return t[p].a;
if (r <= md) return ask(ls, l, r);
if (l > md) return ask(rs, l, r);
return ask(ls, l, r) * ask(rs, l, r);
}
inline void change(int x, int y) {
g[x].a[1][0] += y - w[x], w[x] = y;
while (x) {
mat lst = ask(1, dfn[top[x]], dfn[pot[top[x]]]);
mdf(1, dfn[x]);
mat now = ask(1, dfn[top[x]], dfn[pot[top[x]]]);
x = f[top[x]];
int o = max(now.a[0][0], now.a[1][0]) - max(lst.a[0][0], lst.a[1][0]);
g[x].a[0][0] = g[x].a[0][1] += o;
g[x].a[1][0] += now.a[0][0] - lst.a[0][0];
}
}
int main() {
rd(n), rd(m), rda(w, n);
for (int i = 1, x, y; i < n; i++)
rd(x), rd(y), e[x].pb(y), e[y].pb(x);
for (int i = 1; i <= n; i++)
reverse(e[i].begin(), e[i].end());
d[1] = 1, dfs(1), dfs(1, 1);
for (int i = 1; i <= n; i++)
g[i].a[0][0] = g[i].a[0][1] = G[i][0],
g[i].a[1][0] = G[i][1], g[i].a[1][1] = -inf;
build(1, 1, n);
for (int i = 1, x, y; i <= m; i++) {
rd(x), rd(y), change(x, y);
mat ans = ask(1, 1, dfn[pot[1]]);
print(max(ans.a[0][0], ans.a[1][0]));
}
return 0;
}
参考资料
- OI Wiki 动态 DP
- shadowice1984 题解 P4643 【模板】动态dp
