Dyd's Blog

He who has a strong enough why can bear almost any how.

基环树DP

仙人掌的特殊情况

基环树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]; //s:环上前缀和,sum:成链二倍后的前缀和
LL ans, as;
bool v[N], ins[N];
int cir[N], ed[N], cnt = 0; //cir:所有的环成的链(未二倍),ed:每个环的终点
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) //树形dp
{
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;
}