记录编号	452856	评测结果	AAAAAAAAAA
题目名称	[HAOI 2009]毛毛虫	最终得分	100
用户昵称	Fisher.	是否通过	通过
代码语言	C++	运行时间	0.469 s
提交时间	2017-09-20 15:08:53	内存使用	4.89 MiB

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring> 
#include <vector>
using namespace std;
/*
	d[u]表示：以u为根的子树；最长链及其附属的总数；
	附属就是以他为根，非最长链深度为一的儿子；
	转移：d[u]=儿子数-1+max(d[v])(v是u的儿子)+1;最后加的1是自己；
	也就是
	d[u]=儿子数+max(d[v]); 
	边界：d[叶子]=1;
	答案；每个节点，计算两条最大的链:
	//坑点1   如果只有最大链就不能，ans=max(ans,d[u]-1+cmaxx);这样会多减1 
	//坑点2   如果两个链都存在，如果这个节点有爹，还得带上它爹；
	//蛇皮.... 
	也就是ans=max(d[u]-1+次大链); 
*/
inline int read(){
	int x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
	return x*f;
}
const int maxn=300010;
int n,m;
vector<int>t[maxn];
int d[maxn]; 
int ans=0;
inline void dp(int u,int f){
	d[u]++;//自己 
	//if(u==8)puts("cao");
	if(t[u].size()==1&&t[u][0]==f)return;
	int erzi=t[u].size();//儿子中有一个是父亲（笑哭 
	int maxx=0,cmaxx=0;
	for(int i=0;i<t[u].size();i++){
		int v=t[u][i];
		if(v==f){erzi--;continue;}
		dp(v,u);
		//--------毛毛蛇的蛇头--------- 
		if(d[v]>maxx)
			cmaxx=maxx,maxx=d[v];
		else if(d[v]>cmaxx)
			cmaxx=d[v];
		//---------------------------
	}
	d[u]=d[u]+erzi-1+maxx;
	//------------------毛毛蛇的蛇皮--------- 
	if(erzi>=2){//存在次大链：
		if(t[u].size()>erzi)//mmp毛毛蛇蛇皮的地方；如果从中间撇开，它爹也得算上; 
			ans=max(ans,d[u]+cmaxx);
		else
			ans=max(ans,d[u]-1+cmaxx);
	}
	else{
		ans=max(ans,d[u]);//不存在次大链情况； 
	}
	//---------------------------------------
} 
int main(){
	freopen("worma.in","r",stdin);
	freopen("worma.out","w",stdout);
	n=read();m=read();
	for(int i=1;i<=m;i++){
		int u=read(),v=read();
		t[u].push_back(v);
		t[v].push_back(u);
	}
	dp(1,0);
	printf("%d\n",ans);
	//for(int i=1;i<=n;i++)printf("%d %d\n",i,d[i]);
	return 0;
}