题解 P4719 【模板】动态dp

Tweetuzki

2019-01-15 23:16:21

题解

不得不承认,去年提高组 D2T3 对动态 DP 起到了良好的普及效果。

动态 DP 主要用于解决一类问题。这类问题一般原本都是较为简单的树上 DP 问题,但是被套上了丧心病狂的修改点权的操作。就比如说这道题:

【模板】动态 DP

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

我们首先考虑没有修改的情况下怎么做。首先先选取 1 号点作为全树的根。然后我们设 f_{i, 0} 表示不选择 i 号点时,以 i 号点为根的子树的最大权独立集;f_{i, 1} 表示选择 i 号点时,以 i 号点为根的子树的最大权独立集。我们可以很容易地写出如下的方程:

f_{i, 0} = \sum_{j} \max(f_{j, 0}, f_{j, 1}) f_{i, 1} = \sum_{j} f_{j, 0} + a_i

这里 j 表示 i 号点的所有儿子。特殊地,若点 i 为叶子节点,f_{i, 0} = 0, f_{i, 1} = a_i

最后的答案就是 \max(f_{1, 0}, f_{1, 1})

接下来带上修改。

首先根据动态规划的转移方程可以发现,我们修改了一个点的点权,只会更改从这个点到根这条路径上节点的 DP 值,其他值是不会发生更改的。这时候如果我们要对整棵树重新求一遍最大权独立集,未免太过浪费。所以我们希望能够更改这条链上的 DP 值。

由于树可能会退化成一条链,这样每次更新就是 \mathcal{O(n)} 的,显然不可接受。我们希望这条链只更新 \log n 次……

点分治!抱歉博主太弱了,不会那个被称作“全局平衡二叉树”的厉害做法。

这时候我们请出解决树上问题的神器——重链剖分。

重链剖分有一些性质,这些性质正是它在动态 DP 中能够发挥作用的重要保障。

  1. 每个点到根的路径上,最多经过 \log n 条轻边。也就是说,重链的条数最多也只有 \log n 条。这为动态 DP 的时间复杂度做了保障。
  2. 每条重链的链尾都是叶子节点,且只有叶子节点没有重儿子。这为动态规划的初始状态和转移方式做了保障。
  3. 重链剖分中,一条重链所在的区间在剖出的 DFS 序上,是连续的一段区间。这为可以使用数据结构维护区间信息,达到快速转移做了保障。

那么在宏观上,我们相当于在更新时,对于这些重链暴力地互相转移更新。接下来我们考虑一些微观问题:在一条链里,怎么支持快速修改和查询这条链的 DP 值。

我们保持 f 数组的定义不变。为了迎合重链剖分划分出了轻重儿子,我们形式化地定义 g 数组:g_{i, 1} 表示 i 号点的所有轻儿子,都不取的最大权独立集;g_{i, 0} 表示 i 号点的所有轻儿子,可取可不取形成的最大权独立集。这样就可以把上述的 DP 式子大大简化了(至少没有了那个 \Sigma)。

f_{i, 0} = g_{i, 0} + \max(f_{j, 0}, f_{j, 1}) f_{i, 1} = g_{i, 1} + a_i + f_{j, 0}

这里的 j 表示 i 号点的重儿子。特殊地,对于叶子节点,g_{i, 0} = g_{i, 1} = 0

但是感觉这玩意儿好像不大优美?第二个转移式子中,g_{i, 1}a_i 都只和 i 有关,那么我们不妨把它们合并起来。我们重新定义 g_{i, 1}:表示 i 号点只考虑轻儿子的取自己的最大权独立集。那么这时候,第二个方程就可以变为 f_{i, 1} = g_{i, 1} + f_{j, 0}

但是这玩意儿咋区间维护嘞?回想一下当初学习斐波那契的时候,我们碰到过这样的 DP 方程:

f_i = f_{i - 1} + f_{i - 2}

这个方程涉及上一步的贡献,没法满足结合率,不太舒服。于是我们定义了一个矩阵,化加为乘,于是我们愉快地用快速幂 AC 了。

这道题我们也给它套个矩阵。对于每个点,都表示一个状态,这个状态共有两个值,于是我们考虑维护一个 1 \times 2 的矩阵。

\begin{vmatrix} f_{i, 0} & f_{i, 1} \end{vmatrix}

现在我们要从一个点的重儿子 j 转移到 i 上,也就是说我们需要构造出一个转移矩阵使得 \begin{vmatrix} f_{j, 0} & f_{j, 1} \end{vmatrix} 能够转移到 \begin{vmatrix} f_{i, 0} & f_{i, 1} \end{vmatrix}。但是我们回顾一下这个转移方程(已更改 g_{i, 1} 的定义):

f_{i, 0} = g_{i, 0} + \max(f_{j, 0}, f_{j, 1}) f_{i, 1} = g_{i, 1} + f_{j, 0}

它一点也不满足矩阵乘法的形式啊!

别慌……我们大胆地重定义矩阵乘法!

我们定义一个新的运算符 *,对于矩阵 \mathrm{A}, \mathrm{B},定义 \mathrm{A} * \mathrm{B} 的结果 \mathrm{C},满足:

\mathrm{C}_{i, j} = \max_{k}(\mathrm{A}_{i, k} + \mathrm{B}_{k, j})

实现到代码上,就是

struct Matrix {
  int mat[MaxN][MaxN];
}

inline Matrix operator * (Matrix a, Matrix b) {
  Matrix c;

  for (int i = 0; i < n; ++i)
    for (int j = 0; j < n; ++j)
      for (int k = 0; k < n; ++k)
        c.mat[i][j] = max(c.mat[i][j], a.mat[i][k] + b.mat[k][j]);

  return c;
}

但是这个东西为什么具有结合率呢?

于是我们口胡完了结合率的证明。那么我们就可以用了。接下来我们要构造一个转移矩阵,这个是相对难的一个内容。我就介绍一下我个人构造转移矩阵的拙劣方法吧。

在构造一个转移矩阵之前,我们先想办法把这玩意儿变形,变得和运算 * 差不多。

f_{i, 0} = \max(f_{j, 0} + g_{i, 0}, f_{j, 1} + g_{i, 0}) f_{i, 1} = \max(g_{i, 1} + f_{j, 0}, -\infty)

接着我们把已知的状态和要转移到的状态写在一起,把未知的转移矩阵用 \mathrm{U} 表示。

\begin{vmatrix} f_{j, 0} & f_{j, 1} \end{vmatrix} * \mathrm{U} = \begin{vmatrix} f_{i, 0} & f_{i, 1} \end{vmatrix}

我们原来是一个 1 \times 2 的矩阵,要形成一个 1 \times 2 的矩阵,那么 \mathrm{U} 应当是一个 2 \times 2 的矩阵。那么我们设矩阵左上、右上、左下、右下四个位置分别为 u_1, u_2, u_3, u_4。接下来把每个位置对应上去。

$$\begin{vmatrix} f_{j, 0} & f_{j, 1} \end{vmatrix} * \begin{vmatrix} g_{i, 0} & g_{i, 1} \\ g_{i, 0} & -\infty \end{vmatrix} = \begin{vmatrix} f_{i, 0} & f_{i, 1} \end{vmatrix}$$ 嗯……好像没问题? 这样子,我们对于一条重链,我们的叶子节点就存储了最初始的值,链上每个节点都对应着一个转移矩阵。我们发现这个转移矩阵和重链信息是没有任何关系的,且因为这个矩阵满足结合率,对于一条重链,我们可以之间线段树维护区间乘积(或者叫……“$*$ 积”?)。然后到了一条重链链头,因为这个点是它父亲的轻儿子,我们需要更新它父亲节点所在的点的转移矩阵。这样子一直跳到根节点就可以了。貌似……大功告成? 重链剖分剖出的 DFS 序,由于先访问了链头,所以这个区间中,链头在区间左端,链尾在区间右端。我们存储的初始信息在叶子节点(也就是链尾)上,因此我们的矩阵 $*$ 法应当是转移矩阵在前,要维护的值矩阵在后。我们要把这个矩阵前后换个顺序,再转个个儿,加上一些推算,可以变形成: $$\begin{vmatrix} g_{i, 0} & g_{i, 0} \\ g_{i, 1} & -\infty \end{vmatrix} * \begin{vmatrix} f_{j, 0} \\ f_{j, 1} \end{vmatrix} = \begin{vmatrix} f_{i, 0} \\ f_{i, 1} \end{vmatrix}$$ 这样就真的做完了。最后我写一些关于代码实现的小细节: 1. 对于一个点查其 dp 值,需要从这个点一直查到区间链尾。因此,树剖时我们需要多维护一个 $\texttt{End[i]}$(这里的 $i$ 是一条重链的链头),表示以 $i$ 为链头的这条链,链尾(叶子)节点在 DFS 序上的位置。 2. 更新线段树上某个点的转移矩阵时,传入的如果是矩阵,递归下去常数太大。一个解决方法是,在线段树外,维护一个矩阵组 $\texttt{Val[i]}$,表示每个节点对应的转移矩阵。这样在线段树更新找到对应位置时,直接赋值进来即可。 最后贴上代码。 解释一下变量名: $\texttt{Id[i]}$ 表示 $i$ 号点在 DFS 序中的位置,$\texttt{Dfn[i]}$ 表示在 DFS 序中下标 $i$ 的位置对应的是什么点(与 $\texttt{Id[i]}$ 相反),$\texttt{Fa[i]}$ 是父亲节点,$\texttt{Siz[i]}$ 是子树大小,$\texttt{Dep[i]}$ 是该节点深度(好像没什么用),$\texttt{Wson[i]}$ 是 $i$ 号节点的重儿子,$\texttt{Top[i]}$ 表示 $i$ 号点所在重链链顶编号。 ```cpp #include <iostream> #include <cstdio> #include <cstring> using namespace std; const int MaxN = 100000 + 5, MaxM = 200000 + 5; const int MaxV = 400000 + 5; const int INF = 0x7F7F7F7F; struct Matrix { int mat[2][2]; Matrix() { memset(mat, -0x3F, sizeof mat); } inline Matrix operator * (Matrix b) { Matrix c; for (int i = 0; i < 2; ++i) for (int j = 0; j < 2; ++j) for (int k = 0; k < 2; ++k) c.mat[i][j] = max(c.mat[i][j], mat[i][k] + b.mat[k][j]); return c; } }; int N, M; int cntv, cnte; int A[MaxN]; int Fa[MaxN], Siz[MaxN], Dep[MaxN], Wson[MaxN]; int Top[MaxN], Id[MaxN], Dfn[MaxN], End[MaxN]; int F[MaxN][2]; int Head[MaxN], To[MaxM], Next[MaxM]; Matrix Val[MaxN]; struct SegTree { int L[MaxV], R[MaxV]; Matrix M[MaxV]; inline void Push_up(int i) { M[i] = M[i << 1] * M[i << 1 | 1]; } void Build_Tree(int left, int right, int i) { L[i] = left, R[i] = right; if (L[i] == R[i]) { M[i] = Val[Dfn[L[i]]]; return; } int mid = (L[i] + R[i]) >> 1; Build_Tree(L[i], mid, i << 1); Build_Tree(mid + 1, R[i], i << 1 | 1); Push_up(i); } void Update_Tree(int x, int i) { if (L[i] == R[i]) { // 直接赋值,减小常数 M[i] = Val[Dfn[x]]; return; } int mid = (L[i] + R[i]) >> 1; if (x <= mid) Update_Tree(x, i << 1); else Update_Tree(x, i << 1 | 1); Push_up(i); } // 查询一个点的 DP 值,相当于查询这条重链上链尾矩阵和链中转移矩阵的 '*' 积 Matrix Query_Tree(int left, int right, int i) { if (L[i] == left && R[i] == right) return M[i]; int mid = (L[i] + R[i]) >> 1; if (right <= mid) return Query_Tree(left, right, i << 1); else if (left > mid) return Query_Tree(left, right, i << 1 | 1); else return Query_Tree(left, mid, i << 1) * Query_Tree(mid + 1, right, i << 1 | 1); } } T; inline void add_edge(int from, int to) { cnte++; To[cnte] = to; Next[cnte] = Head[from]; Head[from] = cnte; } void readin() { scanf("%d %d", &N, &M); for (int i = 1; i <= N; ++i) scanf("%d", &A[i]); for (int i = 1; i < N; ++i) { int u, v; scanf("%d %d", &u, &v); add_edge(u, v); add_edge(v, u); } } void dfs1(int u) { Siz[u] = 1; for (int i = Head[u]; i; i = Next[i]) { int v = To[i]; if (v == Fa[u]) continue; Fa[v] = u; Dep[v] = Dep[u] + 1; dfs1(v); Siz[u] += Siz[v]; if (Siz[v] > Siz[Wson[u]]) Wson[u] = v; } } void dfs2(int u, int chain) { cntv++; Id[u] = cntv; Dfn[cntv] = u; Top[u] = chain; End[chain] = max(End[chain], cntv); // 第二次树剖时直接更新 F, G 数组(这里直接将 G 放入矩阵更新) F[u][0] = 0, F[u][1] = A[u]; Val[u].mat[0][0] = Val[u].mat[0][1] = 0; Val[u].mat[1][0] = A[u]; if (Wson[u] != 0) { dfs2(Wson[u], chain); // 依照定义,重儿子不应计入 G 数组 F[u][0] += max(F[Wson[u]][0], F[Wson[u]][1]); F[u][1] += F[Wson[u]][0]; } for (int i = Head[u]; i; i = Next[i]) { int v = To[i]; if (v == Fa[u] || v == Wson[u]) continue; dfs2(v, v); F[u][0] += max(F[v][0], F[v][1]); F[u][1] += F[v][0]; Val[u].mat[0][0] += max(F[v][0], F[v][1]); Val[u].mat[0][1] = Val[u].mat[0][0]; Val[u].mat[1][0] += F[v][0]; } } void init() { readin(); dfs1(1); dfs2(1, 1); } void update_path(int u, int w) { Val[u].mat[1][0] += w - A[u]; A[u] = w; Matrix bef, aft; while (u != 0) { // 计算贡献时,应当用一个 bef 矩阵还原出少掉这个轻儿子的情况,再将 aft 加入更新 bef = T.Query_Tree(Id[Top[u]], End[Top[u]], 1); T.Update_Tree(Id[u], 1); aft = T.Query_Tree(Id[Top[u]], End[Top[u]], 1); u = Fa[Top[u]]; Val[u].mat[0][0] += max(aft.mat[0][0], aft.mat[1][0]) - max(bef.mat[0][0], bef.mat[1][0]); Val[u].mat[0][1] = Val[u].mat[0][0]; Val[u].mat[1][0] += aft.mat[0][0] - bef.mat[0][0]; } } void solve() { T.Build_Tree(1, N, 1); for (int i = 1; i <= M; ++i) { int u, w; scanf("%d %d", &u, &w); update_path(u, w); Matrix Ans = T.Query_Tree(Id[1], End[1], 1); printf("%d\n", max(Ans.mat[0][0], Ans.mat[1][0])); } } int main() { init(); solve(); return 0; } ``` 附:本文同时发布于本蒟蒻的[博客](https://www.cnblogs.com/tweetuzki/p/10274788.html)。