【洛谷P4719】动态dp

柔光的暖阳◎ 2023-06-05 08:53 85阅读 0赞

### 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 ###

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

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 }

AC Code

转载于:https://www.cnblogs.com/shl-blog/p/11365207.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20230601/46a22e041d8545918004ea4f22bf38de.png