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;
const int oo = 1e9;
#define sz(a) (int)a.size()
#define eb emplace_back
using pii = pair<int, int>;
int n;
namespace arcv {
int n;
vector<int> adj[N];
int par[N];
int sz[N];
int st[N];
int en[N];
int tour[N];
int ans = oo;
int times = 0;
multiset<int> S;
void calc_sz(int u, int p) {
par[u] = p;
sz[u] = 1;
for(int v : adj[u]) {
if(v == p)
continue;
calc_sz(v, u);
sz[u] += sz[v];
}
}
int get(int a, int b, int c) {
return max({a, b, c}) - min({a, b, c});
}
void DFS1(int u, int p) {
auto it = S.lower_bound((n - sz[u]) / 2);
if(it != S.end())
ans = min(ans, get(sz[u], *it, n - sz[u] - (*it)));
if(it != S.begin())
--it;
for(int v : adj[u]) {
if(v == p)
continue;
DFS1(v, u);
}
S.emplace(sz[u]);
en[u] = times;
}
void DFS2(int u, int p) {
auto it = S.lower_bound((n + sz[u]) / 2);
if(it != S.end())
ans = min(ans, get((*it) - sz[u], sz[u], n - (*it)));
if(it != S.begin())
--it;
if(it != S.end())
ans = min(ans, get((*it) - sz[u], sz[u], n - (*it)));
S.emplace(sz[u]);
for(int v : adj[u]) {
if(v == p)
continue;
DFS2(v, u);
}
S.erase(S.find(sz[u]));
}
void solution() {
cin >> n;
for(int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
adj[u].eb(v);
adj[v].eb(u);
}
calc_sz(1, 0);
DFS1(1, 0);
S.clear();
DFS2(1, 0);
cout << ans;
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
arcv::solution();
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |