#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 25;
vector <int> adj[MAXN];
int sze[MAXN], n, in[MAXN], out[MAXN], t;
typedef long long ll;
int mn = 1e9; const int bad = -1e9;
void dfs (int pos, int par) {
sze[pos] = 1;
in[pos] = ++t;
int mx = bad;
for (auto j : adj[pos]) {
if (j == par) continue;
dfs(j, pos);
sze[pos] += sze[j];
if (abs(2 * sze[j] - sze[pos]) < abs(2 * mx - sze[pos])) mx = sze[j];
}
if (sze[pos] != 1 && pos != 1) mn = min(mn, max({n - sze[pos], sze[pos] - mx, mx}) - min({n - sze[pos], sze[pos] - mx, mx}));
out[pos] = t;
}
bool check (int x, int y) {
return in[y] < in[x] && in[x] <= out[y];
}
int main () {
cin >> n;
for (int i = 1; i < n; i++) {
int a, b;
cin >> a >> b;
adj[a].push_back(b);
adj[b].push_back(a);
}
dfs(1, -1);
for (int i = 2; i <= n; i++) {
for (int j = i + 1; j <= n; j++) {
if (check(i, j) || check(j, i)) continue;
int x = n - sze[j] - sze[i];
mn = min(mn, max({sze[i], sze[j], x}) - min({sze[i], sze[j], x}));
}
}
cout << mn << '\n';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
7260 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
7260 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
7260 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
7260 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
7260 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
7260 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
