#include<bits/stdc++.h> #define bug(x) cerr<<#x<<" = "<<x<<'\n' using namespace std; const int maxn = 200100, INF = 1e9; int N, ch[maxn], ans; vector <int> G[maxn]; set <int> A, B; void check(int a, int b, int c) { int x = max({a, b, c}); int y = min({a, b, c}); ans = min(ans, x - y); } void prep(int u, int p = -1) { ch[u] = 1; for (int v : G[u]) if (v != p) { prep(v, u); ch[u] += ch[v]; } } void dfs(int u, int p = -1) { auto it = A.lower_bound((N + ch[u]) / 2); check(ch[u], *it - ch[u], N - *it); if (it != A.begin()) { --it; check(ch[u], *it - ch[u], N - *it); } auto ti = B.lower_bound((N - ch[u]) / 2); check(ch[u], *ti, N - ch[u] - *ti); if (ti != B.begin()) { --ti; check(ch[u], *ti, N - ch[u] - *ti); } A.insert(ch[u]); for (int v : G[u]) if (v != p) { dfs(v, u); } A.erase(ch[u]); B.insert(ch[u]); } int main() { ios::sync_with_stdio(0); cin.tie(0); // freopen("cc.inp", "r", stdin); // freopen("cc.out", "w", stdout); cin >> N; for (int u, v, i = 1; i < N; ++i) { cin >> u >> v; G[u].push_back(v); G[v].push_back(u); } ans = INF; prep(1); dfs(1); cout << ans << '\n'; }