仙人掌的特殊情况
基环树DP
前置知识:基环树
包含 $n$ 个点 $n$ 条边的联通图叫做基环树,可以看作一棵树上添加一条边(可重边和自环),这样会形成一个只有一个环的图,可以把环看成一个广义上的根节点,环上的每一个点为根都挂着一棵树(可以为空),所以叫做基环树,当然,很多棵基环树构成一个基环树森林,明显,基环树森林也是点数等于边数的
对于基环树,关键点是处理环
例题一
岛屿
本题大意是要求一个基环树森林中每个基环树的直径,这就是一个非常经典的基环树dp:
考虑某一棵基环树的直径(设为 $u$ 到 $v$ ),若直径不经过环,即 $u,v$ 属于同一棵树,树形dp即可求出直径;若直径经过环,即 $u,v$ 分属于两棵树,两棵树的根节点通过环联通,可以计算出 $u,v$ 各自到根的距离,再计算出环上两根的距离,求和即可
以上是我们知道直径的情况,但实际上,我们并不知道直径是哪两个点,所以必须两种情况都计算:先树形dp处理情况1,再枚举环上的点 $x,y$ (这两个节点必然是某棵树的根),计算情况2,总的时间复杂度 $O(n^2)$ ,必须考虑优化
我们发现树形dp是 $O(n)$ 的,时间主要耗费在情况2的枚举上了
不妨设 $d[x]$ 表示 $x$ 所在树上离 $x$ 最远的点到 $x$ 的距离, $d[y]$ 同理,设 $S(x,y)$ 表示环上从 $x$ 顺时针走到 $y$ 的距离(这样的好处是 $S(x,y)$ 是唯一确定的,并且这样也一定不会漏答案,因为 $x$ 逆时针走到 $y$ 的情况就是 $y$ 顺时针走到 $x$ ),那么对于每一个 $x$ ,我们要在环上找到一个 $y$ , 使 $d[x] + d[y] + S(x, y)$ 最大
明显, $S(x,y)$ 可以转化为前缀和,则原式变为 $d[x] + d[y] + sum[x] - sum[y]$ ,对于确定的 $x$ ,只需要求一个 $d[y] - sum[y]$ 的最大值,考虑经典的把环二倍成链的方法,破环成链,这就是一个典型的滑动窗口问题,单调队列解决,时间复杂度 $O(n)$
代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110
| #include <bits/stdc++.h> #define LL long long using namespace std; const int N = 1000000 + 5; int n; struct Edge { int ne, ver, w; } e[N << 1]; int h[N], idx = 0; int fa[N], fw[N]; int q[N], l, r; LL s[N], d[N << 1], sum[N << 1]; LL ans, as; bool v[N], ins[N]; int cir[N], ed[N], cnt = 0; void add(int x, int y, int z) { e[idx].ver = y, e[idx].w = z, e[idx].ne = h[x], h[x] = idx++; } void dfs_c(int x, int in_e) { v[x] = ins[x] = true; for (int i = h[x], y; i != -1; i = e[i].ne) { if (i == (in_e ^ 1)) continue; y = e[i].ver; fa[y] = x, fw[y] = e[i].w; if (!v[y]) dfs_c(y, i); else if (ins[y]) { ++cnt; ed[cnt] = ed[cnt - 1]; LL _sum = e[i].w; for (int z = x; z != y; z = fa[z]) { s[z] = _sum; cir[++ed[cnt]] = z; _sum += fw[z]; } s[y] = _sum; cir[++ed[cnt]] = y; } } ins[x] = false; } LL dp(int x) { v[x] = true; LL d1 = 0, d2 = 0; for (int i = h[x], y; i != -1; i = e[i].ne) { y = e[i].ver; if (v[y]) continue; LL _d = dp(y) + e[i].w; if (_d >= d1) d2 = d1, d1 = _d; else if (_d > d2) d2 = _d; } as = max(as, d1 + d2); return d1; } int main() { scanf("%d", &n); for (int i = 0; i <= n; ++i) h[i] = -1; for (int i = 1, j, w; i <= n; ++i) { scanf("%d%d", &j, &w); add(i, j, w), add(j, i, w); } for (int i = 1; i <= n; ++i) if (!v[i]) dfs_c(i, -1); for (int i = 1; i <= n; ++i) v[i] = false; for (int i = 1; i <= ed[cnt]; ++i) v[cir[i]] = true; ans = 0; for (int i = 1, si; i <= cnt; ++i) { as = si = 0; for (int j = ed[i - 1] + 1; j <= ed[i]; ++j) { d[++si] = dp(cir[j]); sum[si] = s[cir[j]]; } for (int j = 1; j <= si; ++j) d[si + j] = d[j], sum[si + j] = sum[j] + sum[si]; l = 1, r = 0; for (int j = 1; j <= si * 2; ++j) { while (l <= r && j - q[l] >= si) ++l; if (l <= r) as = max(as, d[j] + sum[j] + d[q[l]] - sum[q[l]]); while (l <= r && d[q[r]] - sum[q[r]] <= d[j] - sum[j]) --r; q[++r] = j; } ans += as; } printf("%lld\n", ans); return 0; }
|
例题二
骑士
给定一个内向基环树森林,要求一个点集,在满足集合中任意两点没有公共边的前提下最大化点权和
这道题和树形dp中没有上司的舞会非常像,区别是本题是基环树,而那道题是树,这样,就有一个明显的方法:删掉环上的一条边 $(x,y)$ ,就转化为没有上司的舞会,设 $f[i][0/1]$ 表示在以 $i$ 为根的子树中不选/选了 $i$ 的最大点权和,以 $x$ 为根做树形dp即可
思考该方法的正确性:若最终答案没有选 $x$ ,那么 $(x,y)$ 没有意义,删去也没有关系, $f[x][0]$ 就是答案;但如果最终答案选了 $x$ 就必然不能选 $y$ 可以再做第二次树形dp,这次强迫不选 $y$ ,答案就是 $f[x][1]$ ,总的时间复杂度为 $O(n)$
像本题这样删去一条环上的边后考虑删去造成的影响,通过强行限定一些条件多次dp求解也是解决基环树dp的常用方法
代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77
| #include <bits/stdc++.h> #define LL long long using namespace std; const int N = 1e6 + 5; const LL INF = 1e18; int n; struct Edge { int ne, ver; } e[N]; int h[N], idx = 0; LL f1[N][2], f2[N][2]; int w[N]; LL ans = 0; bool v[N], ins[N], rme[N]; void add(int x, int y) { e[idx].ver = y, e[idx].ne = h[x], h[x] = idx++; } void dp(int x, int rmn, LL f[][2]) { for (int i = h[x], y; i != -1; i = e[i].ne) { if (rme[i]) continue; y = e[i].ver; dp(y, rmn, f); f[x][0] += max(f[y][0], f[y][1]); } f[x][1] = -INF; if (x != rmn) { f[x][1] = w[x]; for (int i = h[x], y; i != -1; i = e[i].ne) { if (rme[i]) continue; y = e[i].ver; f[x][1] += f[y][0]; } } } void dfs_c(int x) { v[x] = ins[x] = true; for (int i = h[x], y; i != -1; i = e[i].ne) { y = e[i].ver; if (!v[y]) dfs_c(y); else if (ins[y]) { rme[i] = true; dp(y, -1, f1); dp(y, x, f2); ans += max(f1[y][0], f2[y][1]); } } ins[x] = false; } int main() { scanf("%d", &n); for (int i = 0; i <= n; ++i) h[i] = -1; for (int i = 1, j, _w; i <= n; ++i) { scanf("%d%d", &_w, &j); add(j, i); w[i] = _w; } for (int i = 1; i <= n; ++i) if (!v[i]) dfs_c(i); printf("%lld\n", ans); return 0; }
|
例题三
在来看看最后一题
创世纪
和上题类似,考虑断开一条环上的边 $(x,y)$ ,设 $f[i][0/1]$ 表示在以 $i$ 为根的子树中不选/选了 $i$ 最多能选多少个点,转移如下:
$$
f[i][0]=\sum_{j\in son(i)}\max(f[k][0],f[k][1])\
f[i][1]=\max_{j\in son(i)}(f[i][0]-\max(f[j][0],f[j][1])+f[j][0])+1
$$
同样的,做两遍dp,一遍强迫不选 $(x,y)$ ,不必做任何处理, $Ans=\max(f[x][0],f[x][1])$ ;另一遍必选 $(x,y)$ 则一定用 $x$ 去限制 $y$ ,则必不选 $x$ ,必选 $y$, $Ans=f[x][0]$
代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77
| #include <bits/stdc++.h> #define LL long long using namespace std; const int N = 1e6 + 5; const LL INF = 1e18; int n; struct Edge { int ne, ver; } e[N]; int h[N], idx = 0; LL f1[N][2], f2[N][2]; LL ans = 0; bool v[N], ins[N], rme[N]; void add(int x, int y) { e[idx].ver = y, e[idx].ne = h[x], h[x] = idx++; } void dp(int x, int must, LL f[][2]) { for (int i = h[x], y; i != -1; i = e[i].ne) { if (rme[i]) continue; y = e[i].ver; dp(y, must, f); f[x][0] += max(f[y][0], f[y][1]); } if (x == must) { f[x][1] = f[x][0] + 1; f[x][0] = -INF; return ; } f[x][1] = -INF; for (int i = h[x], y; i != -1; i = e[i].ne) { if (rme[i]) continue; y = e[i].ver; f[x][1] = max(f[x][0] - max(f[y][1], f[y][0]) + f[y][0] + 1, f[x][1]); } } void dfs_c(int x) { v[x] = ins[x] = true; for (int i = h[x], y; i != -1; i = e[i].ne) { y = e[i].ver; if (!v[y]) dfs_c(y); else if (ins[y]) { rme[i] = true; dp(y, -1, f1); dp(y, x, f2); ans += max(max(f1[y][0], f1[y][1]), f2[y][0]); } } ins[x] = false; } int main() { scanf("%d", &n); for (int i = 0; i <= n; ++i) h[i] = -1; for (int i = 1, j; i <= n; ++i) { scanf("%d", &j); add(j, i); } for (int i = 1; i <= n; ++i) if (!v[i]) dfs_c(i); printf("%lld\n", ans); return 0; }
|