萌新求调
查看原帖
萌新求调
648660
Name1楼主2022/8/18 17:32
#include<iostream>
#include<cstdio>
#define Rep(i,s,t) for(int i=s;i<=t;i++)
using namespace std;
const int N=3e5+10,M=2e3+10;
int n,m,ans,son[N],dp[N],dp1[N],dp2[N];
int cnt,head[N];
struct Edge{int next,to;}e[N<<2];
inline void add(int u,int v)
{
	e[++cnt]=(Edge){head[u],v};
	head[u]=cnt;
}
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*10+c-'0',c=getchar();
	return x*f;
}
inline void dfs(int u,int fa)
{
	for(int i=head[u];i;i=e[i].next)
	{
		int v=e[i].to;
		if(v==fa) continue;
		dfs(v,u);
		dp[u]=max(dp[u],dp[v]),son[u]++;
		if(dp[v]>=dp1[u]) dp2[u]=dp1[u],dp1[u]=dp[v];
		else dp2[u]=max(dp2[u],dp[v]);
	}
	dp[u]+=son[u];
	if(!son[u]) dp[u]+=1;
	if(son[u]>=1) dp1[u]+=1;
	if(son[u]>=2) dp2[u]+=1;
	ans=max(ans,max(dp1[u]+dp2[u],dp[u]));
}
signed main()
{
	n=read(),m=read();
	Rep(i,1,m)
	{
		int u=read(),v=read();
		add(u,v),add(v,u);
	}	
	dfs(1,0);
	printf("%d",ans);
	return 0;
}
2022/8/18 17:32
加载中...