#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200000 + 5;
int n;
vector<int> g[MAXN];
int sub[MAXN], heavy[MAXN], parent_[MAXN];
int tin[MAXN], tout[MAXN], euler_[MAXN], timer_ = 0;
long long answer = LLONG_MAX;
/* --------- 1st DFS : size, heavy child, euler order --------- */
void dfs_sz(int u, int p = 0)
{
parent_[u] = p;
sub[u] = 1;
int mx = 0;
tin[u] = ++timer_;
euler_[timer_] = u;
for (int v : g[u])
if (v != p)
{
dfs_sz(v, u);
sub[u] += sub[v];
if (sub[v] > mx) mx = sub[v], heavy[u] = v;
}
tout[u] = timer_;
}
/* multiset chứa kích thước các cây con hiện tại */
/* cnt[x] – số lần x xuất hiện (hỗ trợ remove nhanh) */
multiset<int> S;
vector<int> bucket[MAXN]; // bucket[id] = list size trong subtree id
void add_subtree(int u)
{
// đi qua euler để lấy toàn bộ cạnh khác gốc trong cây con u
for (int t = tin[u]; t <= tout[u]; ++t)
{
int v = euler_[t];
if (v == 1) continue; // đỉnh gốc không có cạnh đi lên
S.insert(sub[v]);
bucket[u].push_back(sub[v]);
}
}
void remove_subtree(int u)
{
for (int x : bucket[u]) S.erase(S.find(x));
}
/* tìm giá trị trong multiset S gần nhất với target */
inline void try_update(long long A, long long B, long long t)
{
long long x,y,z, diff;
/* 2 công thức */
/* 1. nested : t , A-t , B */
x = t; y = A - t; z = B;
diff = max({x,y,z}) - min({x,y,z});
answer = min(answer, diff);
/* 2. disjoint: A , t , B-t (chỉ hợp lệ khi B>t , nhưng
nếu B==t hoặc B<t chênh lệch càng lớn → không thể nhỏ hơn
lời giải hiện tại nên không cần ràng buộc) */
x = A; y = t; z = B - t;
if (z>0) {
diff = max({x,y,z}) - min({x,y,z});
answer = min(answer, diff);
}
}
void query(multiset<int> &M, long long target,
long long A, long long B)
{
if (M.empty()) return;
auto it = M.lower_bound((int)target);
if (it != M.end()) try_update(A,B,*it);
if (it != M.begin()) try_update(A,B,*prev(it));
}
/* --------- 2nd DFS : DSU on tree ----------------------------- */
void dfs_dsu(int u, bool keep)
{
/* process light children first */
for (int v : g[u])
if (v != parent_[u] && v != heavy[u])
dfs_dsu(v, false);
/* heavy child with keep = true */
if (heavy[u]) dfs_dsu(heavy[u], true);
/* add every light child’s subtree into S */
for (int v : g[u])
if (v != parent_[u] && v != heavy[u])
{
add_subtree(v);
}
/* add current node’s own edge (if not root) */
if (u != 1) {
S.insert(sub[u]);
}
/* ------------ TÍNH KẾT QUẢ ---------------- */
if (u != 1) // chỉ các cạnh khác rễ mới cắt được
{
long long A = sub[u];
long long B = n - A;
/* 1. cạnh thứ hai bên TRONG cây con u */
// mọi kích thước trong subtree u ngoại trừ sub[u] chính là
// bucket[u] + mọi bucket[light child] + bucket[heavy child] (đã ở S)
// để có "inside", ta chỉ cần nhìn vào S rồi xoá phần Outside
// --> dùng riêng multiset insideSub (đã được build ở bước add) :
multiset<int> inside;
for (int v : g[u])
if (v != parent_[u])
inside.insert(sub[v]); // cạnh ngay dưới u
if (!inside.empty())
{
long long tgt = A / 2;
query(inside, tgt, A, B);
}
/* 2. cạnh thứ hai nằm bên NGOÀI cây con u
=> chính là multiset S sau khi ta đã add toàn bộ subtree u
ngoại trừ sub[u] đã ở trong S.
*/
long long tgt2 = B / 2;
multiset<int> outside = S;
// loại bỏ toàn bộ subtree u (đã add ở thân hàm) để lại phần ngoài
remove_subtree(u);
if (u != 1) outside.erase(outside.find(sub[u]));
query(outside, tgt2, A, B);
add_subtree(u); // khôi phục
}
/* ---------------------------------------------------------- */
if (!keep)
{
remove_subtree(u);
if (u != 1) S.erase(S.find(sub[u]));
}
}
/* ============================================================= */
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
if (!(cin >> n)) return 0;
for (int i = 1; i < n; ++i)
{
int x,y; cin >> x >> y;
g[x].push_back(y);
g[y].push_back(x);
}
dfs_sz(1);
add_subtree(1); // đưa toàn bộ cạnh vào multiset S
dfs_dsu(1, true);
cout << answer << '\n';
return 0;
}
