#include <iostream>
#include <vector>
using namespace std;
vector<int> nei[300005];
int dfs(int u, int p, int md){
vector<int> vec;
int l = -1, r = 0, cnt = 0;
for (int i : nei[u])
if (i != p)
vec.push_back(dfs(i, u, md)), r = max(r, vec.back()), cnt++;
if (cnt >= md)
return r + cnt - md;
while (l + 1 < r){
int mid = (l + r) / 2, sm = cnt;
for (int &i : vec)
sm += max(0, i - mid);
if (sm <= md)
r = mid;
else
l = mid;
}
return r;
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int n;
cin>>n;
for (int i=1;i<n;i++){
int a, b;
cin>>a>>b;
nei[a].push_back(b);
nei[b].push_back(a);
}
int l = 0, r = n;
while (l + 1 < r){
int mid = (l + r) / 2;
if (dfs(1, 1, mid) == 0)
r = mid;
else
l = mid;
}
cout<<r<<'\n';
}
# | 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... |