#include <bits/stdc++.h>
using namespace std;
#define append push_back
#define int long long
const int N=3e6+10,LG=21;
int mod=1e9+7;
vector<int>g[N];
int s=0,deg[N],ans=0,p[N];
void dfs(int node,int ind,int par=-1){
p[node]=par;
ans=max(ans,(s+ind-1)/ind);
for(auto i:g[node]){
if(i==p[node]) continue;
s+=deg[i]-1;
dfs(i,ind+1,node);
s-=deg[i]-1;
}
}
void dfs2(int node,int ind,int par=-1){
ans=max(ans,(s+ind-1)/ind);
for(auto i:g[node]){
if(i==p[node]) continue;
s+=deg[i]-1;
dfs2(i,ind+1,node);
s-=deg[i]-1;
}
}
void solve(int tst){
int n;
cin>>n;
for(int i=1;i<n;i++){
int a,b;
cin>>a>>b;
deg[a]++;
deg[b]++;
g[a].append(b);
g[b].append(a);
}
s=ans=deg[1];
dfs(1,1);
for(int i=2;i<=n;i++) s=deg[i]-1,dfs2(i,1);
cout<<ans<<endl;
}
signed main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int t = 1;
// cin >> t;
for(int i=1;i<=t;i++){
solve(i);
// if(i!=t) cout<<endl;
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |