游客 注册 | 登录
中文 | En

3852 - 毛毛虫

通过次数

0

提交次数

0

时间限制 : 1 秒 内存限制 : 128 MB

对于一棵树，我们可以将某条链和与该链相连的边抽出来，看上去就象成一个毛毛虫，点数越多，毛毛虫就越大。例如下图左边的树（图 1 ）抽出一部分就变成了右边的一个毛毛虫了（图 2 ）。

题目输入

在文本文件 worm.in 中第一行两个整数 N ， M ，分别表示树中结点个数和树的边数。

接下来 M 行，每行两个整数 a, b 表示点 a 和点 b 有边连接（ a, b ≤ N ）。你可以假定没有一对相同的 (a, b) 会出现一次以上。

题目输出

在文本文件 worm.out 中写入一个整数 , 表示最大的毛毛虫的大小。

输入/输出样例

输入格式

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

输出格式

11

C++解答

#include<iostream>
#include<cstdio>
using namespace std;
int n,m,f[300010];
int pr;
struct u
{
	int b;
	int x;
}c[300000*2+100];
int h[300000+10],l;
bool b[300010];
inline void g(int a,int p)
{
	b[a]=1;
	int zd=0,ed=0,ez=0,zzd=f[p];
	for(int i=h[a];i!=0;i=c[i].x)
	{
		int u=c[i].b;
		if(p==u)
		    continue;
		ez++;
		if(!b[u])
		    g(u,a);
		if(f[u]>ed)
		    ed=f[u];
		if(f[u]>=zd)
		{
			ed=zd;
			zd=f[u];
		}
	}
	f[a]=zd+ez;
	if(f[a]==0)
	    f[a]++;
	if(f[a]>pr)
	    pr=f[a];
	if(zzd>ed)
	    ed=zd;
	if(zzd>=zd)
	{
		ed=zd;
		zd=zzd;
	}
	int o=0;
	if(a==1)
	    o=-1;
	if(zd+ed+ez+o>pr)
	{
	    pr=zd+ed+ez+o;
	}
}
inline void gj(int a,int b)
{
	c[++l].b=b;
	c[l].x=h[a];
	h[a]=l;
}
int main()
{
	//freopen("worma.in","r",stdin);
	//freopen("worma.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		int aa,bb;
		scanf("%d%d",&aa,&bb);
		gj(aa,bb);
		gj(bb,aa);
	}
	g(1,0);
	printf("%d",pr);
	getchar();
	getchar();
}
请先登陆