#include<bits/stdc++.h> using namespace std; #define ll long long #define FOR(i,l,r) for(int i = (l), _r = (r); i <= _r; i++) #define FORN(i,r,l) for(int i = (r), _l = (l); i >= _l; i--) #define endl '\n' #define sz(x) (int)x.size() #define fi first #define se second #define pb push_back #define all(v) (v).begin(),(v).end() #define MASK(x) (1LL << (x)) #define BIT(x,i) (((x) >> (i)) & 1) #define ins insert #define segleft id<<1 #define segright id<<1|1 #define ci1(a) cin >> a #define ci2(a, b) cin >> a >> b #define ci3(a, b, c) cin >> a >> b >> c #define ci4(a, b, c, d) cin >> a >> b >> c >> d const int N = 2e5+5; vector<int> edge[N]; int num[N]; int n, ans = INT_MAX; multiset<int> st; void dfs(int u, int p) { num[u] = 1; for(int v : edge[u]) if (v!=p) { dfs(v, u); num[u] += num[v]; } } void dfsth1(int u, int p) { auto idx = st.upper_bound(((n+num[u])/2)); if (idx != st.end()) { int a = num[u]; int b = *idx - num[u]; int c = n - *idx; ans = min(ans, max({a,b,c}) - min({a,b,c})); } if (idx != st.begin()) { --idx; int a = num[u]; int b = *idx - num[u]; int c = n - *idx; ans = min(ans, max({a,b,c}) - min({a,b,c})); } st.insert(num[u]); for(int v : edge[u]) if (v!=p) { dfsth1(v, u); } st.erase(st.find(num[u])); } void dfsth2(int u, int p) { auto idx = st.upper_bound(((n-num[u])/2)); if (idx != st.end()) { int a = num[u]; int b = *idx; int c = n - a - b; ans = min(ans, max({a,b,c}) - min({a,b,c})); } if (idx != st.begin()) { --idx; int a = num[u]; int b = *idx; int c = n - a - b; ans = min(ans, max({a,b,c}) - min({a,b,c})); } for(int v : edge[u]) if (v!=p) { dfsth2(v, u); } st.insert(num[u]); } void Semicolon() { cin >> n; FOR(i, 1, n-1) { int u,v; cin >> u >> v; edge[u].pb(v); edge[v].pb(u); } dfs(1, 0); st.clear(); dfsth1(1, 0); st.clear(); dfsth2(1, 0); cout << ans << endl; } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); //freopen("", "r", stdin); //freopen("", "w", stdout); //freopen("input.txt", "r", stdin); int t = 1; //cin >> t; while(t--) Semicolon(); return 0; }