abcdeffa's Blog

当局者迷，旁观者清。

0%

GMOJ S1008 【仙人图(II)】

发表于 更新于

Description

给你一个有 $n$ 个点，且边权均为 1 的仙人掌，请你求出它的直径。

Solution

考虑设 $f_i$ 表示点 $i$ 向下能够延伸出的最大长度。

对于经过环的一条路径，显然下图这条路径的长度为 $[f_i + f_j + \text{dis}(i, j)]$，其中 $\text{dis}(i, j)$ 表示的是点 $i$ 和点 $j$ 在环上的距离。

树上的距离很好求，考虑如果有环怎么处理。

显然环顶的点的 $f[]$ 值为 $\max [f_i + f_j + \text{dis}(i, j)]$，其中点 $i$ 和点 $j$ 都在同一个环上。

环上距离不好求，于是考虑将环倍长，然后就转为了求链上距离的问题，容易发现可以用单调队列来加速求解，于是时间复杂度降为 $O(n)$。

Code

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
#include <cstdio>
#define maxN 100010
struct Edge{ int x, y, g; } b[maxN << 1];
int Ans = 0, len = 0, cnt = 0;
int f[maxN], h[maxN];
int queue[maxN], mem[maxN];
int stack[maxN], low[maxN], dfn[maxN];
int min (int x, int y)
{
	return x < y ? x : y;
}
int max (int x, int y)
{
	return x > y ? x : y;
}
void ins (int x, int y)
{
	len++;
	b[len].x = x;
	b[len].y = y;
	b[len].g = h[x];
	h[x] = len;
}
void work (int x)
{
	int len = mem[0];
	for(int i = 1;i <= len; i++)
	{
		mem[mem[0] + i] = mem[i];
	}
	len <<= 1;
	int l = 1, r = 0;
	for(int i = 1;i <= len; i++)
	{
		while(l <= r && queue[l] < i - mem[0] / 2)
		{
			l++;
		}
		if(l <= r)
		{
			Ans = max(Ans, f[mem[i]] + f[mem[queue[l]]] + (i - queue[l]));
		}
		while(l <= r && f[mem[queue[r]]] - queue[r] < f[mem[i]] - i)
		{
			r--;
		}
		queue[++r] = i;
	}
	for(int i = 2;i <= mem[0]; i++)
	{
		f[x] = max(f[x], f[mem[i]] + min(i - 1, mem[0] + 1 - i));
	}
}
void tar (int x)
{
	stack[++stack[0]] = x;
	low[x] = dfn[x] = ++cnt;
	for(int i = h[x];i;i = b[i].g)
	{
		int y = b[i].y;
		if(!dfn[y])
		{
			tar(y);
			low[x] = min(low[x], low[y]);
			if(dfn[x] <= low[y])
			{
				mem[0] = 0;
				mem[++mem[0]] = x;
				int now = 0;
				do
				{
					now = stack[stack[0]--];
					mem[++mem[0]] = now;
				}
				while(now != y);
				work(x);
			}
		}
		else
		{
			low[x] = min(low[x], dfn[y]);
		}
	}
}
int main ()
{
	int n = 0, T = 0;
	scanf("%d %d", &n, &T);
	while(T--)
	{
		int N = 0, last = 0;
		scanf("%d", &N);
		for(int i = 1;i <= N; i++)
		{
			int x = 0;
			scanf("%d", &x);
			if(last)
			{
				ins(x, last);
				ins(last, x);
			}
			last = x;
		}
	}
	tar(1);
	printf("%d", Ans);
	return 0;
}