- 竞赛3班7.26日测试
213333
- @ 2025-7-26 18:02:27

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=3e5+10;
vector<int>edg[N];
int n,u,v;
int value[N],dep[N],addt[N];
void dfs(int x,int f){
int tmp=0,tmp2=0;
for(auto t:edg[x]){
if(t==f)continue;
dfs(t,x);
value[x]=max(value[x],value[t]+1);
if(dep[x]==dep[t]+1){
tmp++;
}
if(dep[x]<dep[t]+1){
dep[x]=dep[t]+1;
tmp=0;
tmp2=t;
}
}
if(tmp!=0 || (tmp2!=0 && addt[tmp2]==1)){
addt[x]=1;
value[x]--;
}
return ;
}
signed main(){
cin>>n;
for(int i=1;i<n;i++){
cin>>u>>v;
edg[u].push_back(v);
edg[v].push_back(u);
}
dfs(1,0);
int ans=0,maxx=-1e9;
for(int i=1;i<=n;i++){
ans+=dep[i];
maxx=max(value[i],maxx);
}
cout<<ans-maxx;
return 0;
}
0 comments
No comments so far...