「BZOJ1023」[SHOI2008]cactus仙人掌图

Description

如果某个无向连通图的任意一条边至多只出现在一条简单回路(simple cycle)里,我们就称这张图为仙人掌
图(cactus)。所谓简单回路就是指在图上不重复经过任何一个顶点的回路。

举例来说,上面的第一个例子是一张仙人图,而第二个不是——注意到它有三条简单回路:(4,3,2,1,6,5,4)(4,3,2,1,6 ,5,4)(7,8,9,10,2,3,7)(7,8,9,10,2,3,7)以及(4,3,7,8,9,10,2,1,6,5,4)(4,3,7,8,9,10,2,1,6,5,4),而(2,3)(2,3)同时出现在前两个的简单回路里。另外,第三张图也不是仙人图,因为它并不是连通图。显然,仙人图上的每条边,或者是这张仙人图的桥(bridge),或者在且仅在一个简单回路里,两者必居其一。定义在图上两点之间的距离为这两点之间最短路径的距离。定义一个图的直径为这张图相距最远的两个点的距离。现在我们假定仙人图的每条边的权值都是1,你的任务是求出给定的仙人图的直径。

Input

输入的第一行包括两个整数nnm(1n50000m(1\leq n\leq 50000以及0m10000)0\leq m\leq 10000)。其中nn代表顶点个数,我们约定图中的顶
点将从11nn编号。接下来一共有mm行。代表m条路径。每行的开始有一个整数k(2k1000)k(2\leq k\leq 1000),代表在这条路径上
的顶点个数。接下来是kk11nn之间的整数,分别对应了一个顶点,相邻的顶点表示存在一条连接这两个顶点的边
。一条路径上可能通过一个顶点好几次,比如对于第一个样例,第一条路径从33经过88,又从88返回到了33,但是我们
保证所有的边都会出现在某条路径上,而且不会重复出现在两条路径上,或者在一条路径上出现两次。

Output

只需输出一个数,这个数表示仙人图的直径长度。

Sample Input

1
2
3
4
5
6
15 3
9 1 2 3 4 5 6 7 8 3
7 2 9 10 11 12 13 10
5 2 14 9 15 10 8
10 1
10 1 2 3 4 5 6 7 8 9 10

Sample Output

1
2
8
9

HINT

对第一个样例的说明:如图,66号点和1212号点的最短路径长度为88,所以这张图的直径为88

Solution

环和链分别考虑。
链直接fx=max{fx+fy+1}f_x=\max\{f_x + f_y + 1\}
环上是由两个点合并过来的,ans=max{fx+fy+disx,y}ans=\max\{f_x+f_y+dis_{x,y}\} disx,ydis_{x,y}xxyy在环上的距离。
环上按照顺序,从11tt枚举一下,然后对于每一个枚举的ii,求最大fy+disi,yf_y+dis_{i,y}
对于前面的点,disi,ydis_{i,y}都是同时单调递增,只要维护fyf_y最大值。注意队列里要保证最大距离是小于半环的。
为了方便,环拆成两倍,破环成链。
我直接无脑建立圆方树,然后直接算直径,错了。zz

这个数据就不行了。
方点是22,那么如果2244直接算,直接萎了,因为要知道环上距离呀。

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<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<map>
#include<bitset>
#define mk make_pair
#define fi first
#define nd second
#define pii pair<int,int>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}
const int N = 51000 * 2, M = 510000;
int n, m, tot;
int ans;
struct G2 {
struct Edge {
int u, v, nxt, w;
}e[M * 2];
int head[N], en;
void addedge(int x, int y, int z) {
e[++en].u = x, e[en].v = y, e[en].nxt = head[x], head[x] = en;
e[en].w = z;
}
int f[N], g[N];
void dfs(int x, int F) {
for(int i = head[x]; i; i = e[i].nxt) {
int y = e[i].v;
if(y == F) continue;
dfs(y, x);
if(f[y] + e[i].w > f[x]) g[x] = f[x], f[x] = f[y] + e[i].w;
else if(f[y] + e[i].w > g[x]) g[x] = f[y] + e[i].w;
}
ans = max(ans, f[x] + g[x]);
}
}g2;
struct G1 {
struct Edge {
int u, v, nxt;
}e[M * 2];
int head[N], en;
void addedge(int x, int y) {
e[++en].u = x, e[en].v = y, e[en].nxt = head[x], head[x] = en;
}
int dfn[N], low[N], num;
int fa[N];
int sum[N];
void solve(int x, int F) {
++tot;
sum[tot] = 1;
int i = x;
while(i != F) {
sum[i] = sum[tot];
++sum[tot];
i = fa[i];
}
i = x;
while(i != F) {
int val = min(sum[i], sum[tot] - sum[i]);
g2.addedge(tot, i, val);
g2.addedge(i, tot, val);
i = fa[i];
}
g2.addedge(tot, F, 0);
g2.addedge(F, tot, 0);
}
void tarjan(int x, int F) {
dfn[x] = low[x] = ++num;
for(int i = head[x]; i;i = e[i].nxt) {
int y = e[i].v;
if(y == F) continue;
if(!dfn[y]) {
fa[y] = x;
tarjan(y, x);
low[x] = min(low[x], low[y]);
} else low[x] = min(low[x], dfn[y]);
if(low[y] <= dfn[x]) continue;
g2.addedge(x, y, 1);
g2.addedge(y, x, 1);
}
for(int i = head[x]; i;i = e[i].nxt) {
int y = e[i].v;
if(fa[y] == x || low[y] != dfn[x]) continue;
solve(y, x);
}
}
}g1;

int main() {
n = read(), m = read(),tot = n;
for(int i = 1; i <= m; ++i) {
int k = read();
int pre;
for(int j = 1; j<= k; ++j) {
int x = read();
if(j > 1) g1.addedge(pre, x), g1.addedge(x, pre);
pre = x;
}
}
g1.tarjan(1, 0);
g2.dfs(1, 0);
writeln(ans);
return 0;
}

std

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
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<map>
#include<bitset>
#define mk make_pair
#define fi first
#define nd second
#define pii pair<int,int>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}
const int N = 51000 * 2, M = 510000;
int n, m;
int ans;
int f[N];
struct G1 {
struct Edge {
int u, v, nxt;
}e[M * 2];
int head[N], en;
void addedge(int x, int y) {
e[++en].u = x, e[en].v = y, e[en].nxt = head[x], head[x] = en;
}
int dfn[N], low[N], num;
int fa[N], tot, a[N*2];
int q[N*2], h, t;
void solve(int x, int F) {
tot = 0;
for(int i = x; i != fa[F]; i = fa[i]) a[++tot] = i;
for(int i = 1; i <= tot; ++i) a[i + tot] = a[i];
q[h = t = 1] = 1;
f[0] = -1e9;
for(int i = 2; i <= tot * 2; ++i) {
while(h <= t && i - q[h] > tot / 2) ++h;
ans = max(ans, f[a[i]] + f[a[q[h]]] + i - q[h]);
while(h <= t && f[a[i]] >= f[a[q[t]]] + i - q[t]) --t;
q[++t] = i;
}
for(int i = 1; i <= tot; ++i) f[F] = max(f[F], f[a[i]] + min(tot - i, i));
ans = max(ans, f[F]);
}
void tarjan(int x, int F) {
dfn[x] = low[x] = ++num;
for(int i = head[x]; i;i = e[i].nxt) {
int y = e[i].v;
if(y == F) continue;
if(!dfn[y]) {
fa[y] = x;
tarjan(y, x);
low[x] = min(low[x], low[y]);
} else low[x] = min(low[x], dfn[y]);
if(low[y] <= dfn[x]) continue;
ans = max(ans, f[x] + f[y] + 1);
f[x] = max(f[x], f[y] + 1);
ans = max(ans, f[x]);
}
for(int i = head[x]; i;i = e[i].nxt) {
int y = e[i].v;
if(fa[y] == x || low[y] != dfn[x]) continue;
solve(y, x);
}
}
}g1;

int main() {
n = read(), m = read();
for(int i = 1; i <= m; ++i) {
int k = read();
int pre;
for(int j = 1; j<= k; ++j) {
int x = read();
if(j > 1) g1.addedge(pre, x), g1.addedge(x, pre);
pre = x;
}
}
g1.tarjan(1, 0);
writeln(ans);
return 0;
}