【洛谷P4719】动态dp-蒲公英云

Description

给定一棵树，点带点权，允许修改点权，求每次修改之后树的最大独立集

Solution

ddp用LCT维护

前置知识（静态树的最大独立集问题）

首先，我们要明确静态树的最大独立集的解法

定义$f[i][0/1]$表示在以$i$为根的子树中，该节点选/不选的最大权值，那么有状态转移方程

\left\{
\begin{matrix}
f[i][0]=\sum\limits_{j\in son(i)}{max\{f[j][0],f[j][1]\}} \\
f[i][1]=val[i]+\sum\limits_{j\in son(i)}{f[j][0]}
\end{matrix}
\right.

我们可以通过一遍dfs在$O(n)$的时间内求出

简化版问题

假定现在这道题不是一棵树而是一个序列，允许修改点权，并且要求求出若干个两两不相邻的点的最大权值和

状态定义类似：定义$f[i][0/1]$表示在前$i$个元素中，$i$选/不选的最大权值，那么有状态转移方程

\left\{
\begin{matrix}
f[i][0]=max\{f[i-1][1],f[i-1][0]\} \\
f[i][1]=val[i]+f[i-1][0]
\end{matrix}
\right.

矩阵优化转移

我们将转移用矩阵进行优化，并且重新定义矩阵乘法的含义，假定$C=A\times B$，那么有

C_{i,j}=\max\limits_{k\in [1, j]}\{A_{i,k}+B_{k,j}\}

因此，转移可以写成这样

\begin{bmatrix}
0 & 0 \\
val[i] & -\infty
\end{bmatrix}
\times
\begin{bmatrix}
f[i-1][0] \\
f[i-1][1]
\end{bmatrix}
=
\begin{bmatrix}
f[i][0] \\
f[i][1]
\end{bmatrix}

所以我们转移时将这些矩阵乘起来就好了

可以用线段树维护，时间复杂度$O(mlogn)$

（真的）动态dp

现在我们把这个问题搬到了树上

再套一个LCT维护即可

我们定义状态，$g[i][1/0]$表示在以$i$为根的子树中，轻儿子及其子树的dp值，那么有状态转移方程

\left\{
\begin{matrix}
g[i][0]=\sum\limits_{j\in lightson(i)}{max\{f[j][0],f[j][1]\}} \\
g[i][1]=val[i]+\sum\limits_{j\in lightson(i)}{f[j][0]}
\end{matrix}
\right.

同时，$f$也可以维护：

\left\{
\begin{matrix}
f[i][0]=g[i][0]+ \max\{f[i.heavyson][0],f[i.heavyson][1]\} \\
f[i][1]=g[i][1]+f[i.heavyson][0]
\end{matrix}
\right.

同样用矩阵优化转移：

\begin{bmatrix}
g[i][0] & g[i][0] \\
g[i][1] & -\infty
\end{bmatrix}
\times
\begin{bmatrix}
f[i.heavyson][0] \\
f[i.heavyson][1]
\end{bmatrix}
=
\begin{bmatrix}
f[i][0] \\
f[i][1]
\end{bmatrix}

这样，我们用LCT就能维护这个dp了

时间复杂度为$O(mlogn)$

Code

1 #include <bits/stdc++.h>
  2 using namespace std;
  3 typedef long long ll;
  4 const int N = 1e5 + 10;
  5 const int INF = 0x3f3f3f3f;
  6 inline int read() {
  7     int ret = 0, op = 1;
  8     char c = getchar();
  9     while (!isdigit(c)) {
 10         if (c == '-') op = -1; 
 11         c = getchar();
 12     }
 13     while (isdigit(c)) {
 14         ret = (ret << 3) + (ret << 1) + c - '0';
 15         c = getchar();
 16     }
 17     return ret * op;
 18 }
 19 struct Edge {
 20     int nxt, to;
 21 } e[N << 1];
 22 struct Matrix {
 23     int m[2][2];
 24     Matrix() {memset(m, 0, sizeof(m));}
 25     inline void build(int x, int y) {
 26         m[0][0] = m[0][1] = x;
 27         m[1][0] = y; m[1][1] = -INF;
 28     }
 29     inline int getmax() {
 30         return max(m[0][0], m[1][0]);
 31     }
 32     Matrix operator *(const Matrix &x) const {
 33         Matrix ret;
 34         for (register int i = 0; i < 2; ++i)
 35             for (register int j = 0; j < 2; ++j)
 36                 for (register int k = 0; k < 2; ++k)
 37                     ret.m[i][j] = max(ret.m[i][j], m[i][k] + x.m[k][j]);
 38         return ret; 
 39     }
 40 };
 41 struct LCT {
 42     int fa, ch[2], f[2];
 43     Matrix x;
 44 } a[N];
 45 int num, head[N], n, m, val[N];
 46 inline void add(int from, int to) {
 47     e[++num].nxt = head[from];
 48     e[num].to = to;
 49     head[from] = num;
 50 }
 51 void dfs(int now, int fa) {
 52     a[now].f[1] = val[now];
 53     for (register int i = head[now]; i; i = e[i].nxt) {
 54         int to = e[i].to;
 55         if (to == fa) continue ;
 56         a[to].fa = now;
 57         dfs(to, now);
 58         a[now].f[0] += max(a[to].f[0], a[to].f[1]);
 59         a[now].f[1] += a[to].f[0];
 60     }
 61     a[now].x.build(a[now].f[0], a[now].f[1]);
 62 }
 63 inline int isnroot(int now) {
 64     return a[a[now].fa].ch[1] == now || a[a[now].fa].ch[0] == now;
 65 }
 66 inline void update(int now) {
 67     a[now].x.build(a[now].f[0], a[now].f[1]);
 68     if (a[now].ch[0]) a[now].x = a[a[now].ch[0]].x * a[now].x;
 69     if (a[now].ch[1]) a[now].x = a[now].x * a[a[now].ch[1]].x;
 70 }
 71 inline void rotate(int x) {
 72     int y = a[x].fa;
 73     int z = a[y].fa;
 74     int xson = a[y].ch[1] == x;
 75     int yson = a[z].ch[1] == y;
 76     int B = a[x].ch[xson ^ 1];
 77     if (isnroot(y)) a[z].ch[yson] = x;
 78     a[y].ch[xson] = B;
 79     a[x].ch[xson ^ 1] = y;
 80     if (B) a[B].fa = y;
 81     a[y].fa = x;
 82     a[x].fa = z;
 83     update(y);
 84     update(x);
 85 }
 86 void splay(int x) {
 87     while (isnroot(x)) {
 88         int y = a[x].fa;
 89         int z = a[y].fa;
 90         if (isnroot(y))
 91             (a[y].ch[0] == x) ^ (a[z].ch[0] == y) ? rotate(x) : rotate(y); 
 92         rotate(x);
 93     }
 94     update(x);
 95 }
 96 void access(int x) {
 97     for (register int y = 0; x; y = x, x = a[x].fa) {
 98         splay(x);
 99         if (a[x].ch[1]) {
100             a[x].f[0] += a[a[x].ch[1]].x.getmax();
101             a[x].f[1] += a[a[x].ch[1]].x.m[0][0];
102         }
103         if (y) {
104             a[x].f[0] -= a[y].x.getmax();
105             a[x].f[1] -= a[y].x.m[0][0];
106         }
107         a[x].ch[1] = y;
108         update(x);
109     }
110 }
111 int main() {
112     n = read(); m = read();
113     for (register int i = 1; i <= n; ++i) val[i] = read();
114     for (register int i = 1; i < n; ++i) {
115         int x = read(), y = read();
116         add(x, y); add(y, x);
117     }
118     dfs(1, 0);
119     while (m--) {
120         int x = read();
121         int y = read();
122         access(x);
123         splay(x);
124         a[x].f[1] += y - val[x];
125         val[x] = y;
126         update(x);
127         splay(1);
128         printf("%d\n", a[1].x.getmax());
129     }
130     return 0;
131 }