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 maxn = 2e5 + 5;
int n;
int sz[maxn];
vector<int> g[maxn];
int ans;
void pre_dfs(int u, int prev) {
sz[u] = 1;
for(auto v:g[u]) {
if(v == prev) continue;
pre_dfs(v, u);
sz[u] += sz[v];
}
}
multiset<int> a, b;
int calc(int a, int b, int c) {
return max({a, b, c}) - min({a, b, c});
}
void dfs(int u, int prev) {
for(auto v:g[u]) {
if(v == prev) continue;
a.insert(sz[u]);
auto it = a.lower_bound((n + sz[v]) / 2);
if(it != a.end()) {
int y = *it;
ans = min(ans, calc(sz[v], y - sz[v], n - y));
// cerr << "a " << v << " " << sz[v] << " " << y << " " << ans << endl;
}
if(it != a.begin()) {
--it;
int y = *it;
ans = min(ans, calc(sz[v], y - sz[v], n - y));
// cerr << "a " << v << " " << sz[v] << " " << y << " " << ans << endl;
}
it = b.lower_bound((n - sz[v]) / 2);
if(it != b.end()) {
int y = *it;
ans = min(ans, calc(sz[v], y, n - sz[v] - y));
// cerr << "b " << v << " " << sz[v] << " " << y << " " << ans << endl;
}
if(it != b.begin()) {
--it;
int y = *it;
ans = min(ans, calc(sz[v], y, n - sz[v] - y));
// cerr << "b " << v << " " << sz[v] << " " << y << " " << ans << endl;
}
dfs(v, u);
a.erase(a.find(sz[u]));
}
b.insert(sz[u]);
}
void solve() {
cin >> n;
for(int i = 1; i < n; ++i) {
int u, v; cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
ans = n + 1;
pre_dfs(1, 0);
dfs(1, 0);
cout << ans;
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
solve();
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |