#include "bits/stdc++.h"
#define endl '\n'
#define fi first
#define se second
constexpr int maxn = 2e5+5;
constexpr int inf = 1e9;
constexpr int mod = 1e9+7;
using namespace std;
using lint = long long;
using pii = pair<int,int>;
int n, ans;
vector<int> adj[maxn];
int sub[maxn];
map<int, int> a, b;
void calcsub(int u) {
sub[u] = 1;
for(int v : adj[u]) {
if(sub[v])
continue;
calcsub(v);
sub[u] += sub[v];
}
}
void calcans(int u) {
map<int, int>::iterator it;
int mx, mn;
it = a.lower_bound((n + sub[u] + 1) / 2);
if(it != a.end()) {
int x = it->fi;
mx = max({sub[u], x - sub[u], n - x});
mn = min({sub[u], x - sub[u], n - x});
ans = min(ans, mx - mn);
}
if(it != a.begin()) {
it--;
int x = it->fi;
mx = max({sub[u], x - sub[u], n - x});
mn = min({sub[u], x - sub[u], n - x});
ans = min(ans, mx - mn);
}
it = b.lower_bound((n - sub[u] + 1) / 2);
if(it != b.end()) {
int x = it->fi;
mx = max({sub[u], x, n - sub[u] - x});
mn = min({sub[u], x, n - sub[u] - x});
ans = min(ans, mx - mn);
}
if(it != b.begin()) {
it--;
int x = it->fi;
mx = max({sub[u], x, n - sub[u] - x});
mn = min({sub[u], x, n - sub[u] - x});
ans = min(ans, mx - mn);
}
}
void dfs(int u) {
calcans(u);
a[sub[u]]++;
for(int v : adj[u]) {
if(a[sub[v]])
continue;
dfs(v);
}
a[sub[u]]--;
if(!a[sub[u]])
a.erase(sub[u]);
b[sub[u]]++;
}
signed main() {
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for(int i = 1, x, y; i < n; i++) {
cin >> x >> y;
adj[x].push_back(y);
adj[y].push_back(x);
}
ans = inf;
calcsub(1);
dfs(1);
cout << ans << endl;
}
Compilation message
papricice.cpp: In function 'int main()':
papricice.cpp:76:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
76 | freopen("in.txt","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~
papricice.cpp:77:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
77 | freopen("out.txt","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
5068 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
5068 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
5068 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
