比赛 |
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;
}