比赛 2024国庆练习2 评测结果 WWAAAAAAAA
题目名称 消防演练 最终得分 80
用户昵称 flyfree 运行时间 0.339 s
代码语言 C++ 内存使用 8.08 MiB
提交时间 2024-10-05 15:59:47
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define MAXN 200010
inline ll read(){
	ll 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;
}
ll n,ans,idx,maxz;
ll hd[MAXN],nxt[MAXN*2],ed[MAXN*2];
ll son[MAXN],dp[MAXN];
void build(ll x,ll y){
	nxt[++idx]=hd[x];
	ed[idx]=y;
	hd[x]=idx;
}
void dfs(ll now,ll fa){
	for(int i=hd[now];i;i=nxt[i]){
		ll y=ed[i];
		if(y==fa)continue;
		son[now]++;
		dfs(y,now);
//		dp[now]=max(dp[now],dp[y]);
	}
	maxz=max(maxz,son[now]);
	if(!son[now]){
		dp[now]=0;
//		cout<<"now: "<<now<<" "<<0<<endl;
		return;
	}
	dp[now]=son[now];
	for(int i=hd[now];i;i=nxt[i]){
		ll y=ed[i];
		ans=max(ans,dp[now]+dp[y]-1+(ll)(fa?1:0));
		dp[now]=max(dp[now],dp[y]+son[now]-1);
	}
	ans=max(ans,dp[now]+(ll)(fa?1:0));
//	cout<<"now: "<<now<<" "<<dp[now]<<endl;
}
int main(){
	freopen("drill.in","r",stdin);
	freopen("drill.out","w",stdout);
	n=read();
	for(int i=1;i<n;i++){
		ll x=read(),y=read();
		build(x,y);
		build(y,x);
	}
	dfs(1,0);
//	cout<<maxz<<endl;
	cout<<ans;
	return 0;
}