Dyd's Blog

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

基环树DP

Posted on Edited on In
Symbols count in article: 6k Reading time ≈ 5 mins.

仙人掌的特殊情况

基环树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;
}