// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>
using namespace std;
#define nl '\n'
#define pb push_back
#define sz(x) int(x.size())
template<class T> using V = vector<T>;
using vi = V<int>;
const int INF = 1e9 + 10;
int main() {
cin.tie(0)->sync_with_stdio(0);
int N; cin >> N;
V<vi> adj(N); for(int i = 0; i < N - 1; i++) {
int u, v; cin >> u >> v; --u, --v;
adj[u].pb(v);
adj[v].pb(u);
}
vi sub(N);
function<void(int, int)> gen = [&](int u, int p) {
sub[u] = 1;
for(auto& v : adj[u]) if (v != p) {
gen(v, u); sub[u] += sub[v];
}
};
gen(0, -1);
int ans = INF; multiset<int> P, R; // parents and rest
function<void(int, int)> dfs = [&](int u, int p) {
if (sz(P)) { // PARENT -> S_u, S_v - S_u, N - S_v
int opt = (sub[u] + N) / 2;
// cout << u << " == PAR => " << opt << endl;
auto it = P.upper_bound(opt);
if (it != end(P)) {
int sv = *it;
// cout << sv << endl;
ans = min(ans, max({sub[u], sv - sub[u], N - sv}) - min({sub[u], sv - sub[u], N - sv}));
}
if (it != begin(P)) {
int sv = *prev(it);
// cout << sv << endl;
ans = min(ans, max({sub[u], sv - sub[u], N - sv}) - min({sub[u], sv - sub[u], N - sv}));
}
// cout << u << " == PAR => " << opt << endl;
}
if (sz(R)) { // REST -> S_u, S_v, N - S_v - S_u
int opt = (N - sub[u]) / 2;
// cout << u << " == REST => " << opt << endl;
auto it = R.upper_bound(opt);
if (it != end(R)) {
int sv = *it;
// cout << sv << endl;
ans = min(ans, max({sub[u], sv, N - sub[u] - sv}) - min({sub[u], sv, N - sub[u] - sv}));
}
if (it != begin(R)) {
int sv = *prev(it);
// cout << sv << endl;
ans = min(ans, max({sub[u], sv, N - sub[u] - sv}) - min({sub[u], sv, N - sub[u] - sv}));
}
// cout << u << " == REST => " << opt << endl;
}
P.insert(sub[u]);
for(auto& v : adj[u]) if (v != p) {
dfs(v, u);
}
P.erase(P.find(sub[u]));
R.insert(sub[u]);
};
dfs(0, -1);
cout << ans << nl;
exit(0-0);
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
344 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
456 KB |
Output is correct |
5 |
Correct |
0 ms |
344 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
344 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
456 KB |
Output is correct |
5 |
Correct |
0 ms |
344 KB |
Output is correct |
6 |
Correct |
1 ms |
604 KB |
Output is correct |
7 |
Correct |
1 ms |
604 KB |
Output is correct |
8 |
Correct |
2 ms |
604 KB |
Output is correct |
9 |
Correct |
1 ms |
604 KB |
Output is correct |
10 |
Correct |
1 ms |
604 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
344 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
456 KB |
Output is correct |
5 |
Correct |
0 ms |
344 KB |
Output is correct |
6 |
Correct |
1 ms |
604 KB |
Output is correct |
7 |
Correct |
1 ms |
604 KB |
Output is correct |
8 |
Correct |
2 ms |
604 KB |
Output is correct |
9 |
Correct |
1 ms |
604 KB |
Output is correct |
10 |
Correct |
1 ms |
604 KB |
Output is correct |
11 |
Correct |
152 ms |
24160 KB |
Output is correct |
12 |
Correct |
154 ms |
24008 KB |
Output is correct |
13 |
Correct |
138 ms |
24392 KB |
Output is correct |
14 |
Correct |
144 ms |
24200 KB |
Output is correct |
15 |
Correct |
140 ms |
24104 KB |
Output is correct |
16 |
Correct |
95 ms |
24008 KB |
Output is correct |
17 |
Correct |
130 ms |
24148 KB |
Output is correct |
18 |
Correct |
149 ms |
30288 KB |
Output is correct |
19 |
Correct |
176 ms |
24188 KB |
Output is correct |
20 |
Correct |
133 ms |
24072 KB |
Output is correct |