This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5, INF = 1e9 + 5;
int n, a, b, cnt[N], ans = INF;
multiset<int> anc, oth;
vector<int> tree[N];
void dfs(int v, int p = 0){
cnt[v] = 1;
for(auto e : tree[v]){
if(e != p){
dfs(e, v);
cnt[v] += cnt[e];
}
}
}
void getans(int x){
int y, z;
if(!anc.empty()){
auto it = anc.lower_bound((n + x) / 2);
if(it != anc.end()){
y = *it - x, z = n - *it;
ans = min(ans, max({x, y, z}) - min({x, y, z}));
}
if(it != anc.begin()){
it = prev(it);
y = *it - x, z = n - *it;
ans = min(ans, max({x, y, z}) - min({x, y, z}));
}
}
if(!oth.empty()){
auto it = oth.lower_bound((n - x) / 2);
if(it != oth.end()){
y = *it, z = n - x - y;
ans = min(ans, max({x, y, z}) - min({x, y, z}));
}
if(it != oth.begin()){
it = prev(it);
y = *it, z = n - x - y;
ans = min(ans, max({x, y, z}) - min({x, y, z}));
}
}
}
void solve(int v, int p = 0){
getans(cnt[v]);
anc.insert(cnt[v]);
for(auto e : tree[v]){
if(e != p) solve(e, v);
}
anc.erase(anc.find(cnt[v]));
oth.insert(cnt[v]);
}
int main(){
ios_base::sync_with_stdio(false);cin.tie(NULL);
cin >> n;
for(int i = 0; i < n - 1; i++){
cin >> a >> b;
tree[a].push_back(b);
tree[b].push_back(a);
}
dfs(1);
solve(1);
cout << ans;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |