#include<bits/stdc++.h> using namespace std; #define ll long long #define pb push_back #define fi first #define se second int n; vector<vector<int>> dzie, graf, ilegl; vector<int> ojc, gl; void dfs(int w) { for (int i : graf[w]) { if (i == ojc[w]) continue; ojc[i] = w; gl[i] = gl[w] + 1; ilegl[gl[i]].pb(i); dzie[w].pb(i); dfs(i); } } bool czy(int bud) { vector<int> potrzeba(n + 1, 0); for (int i = n; i >= 0; i--) { //cout << "glebokosc " << i << endl; ll wym = 0; for (int w : ilegl[i]) { //cout << w << " "; potrzeba[w] = dzie[w].size() - bud; for (int d : dzie[w]) potrzeba[w] += potrzeba[d]; potrzeba[w] = max(potrzeba[w], 0); //cout << "potrzeba: " << potrzeba[w] << endl; } } if (potrzeba[1] > 0) return 0; return 1; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int a, b; cin >> n; ojc.resize(n + 1); dzie.resize(n + 1); graf.resize(n + 1); ilegl.resize(n + 1); gl.resize(n + 1); for (int i = 0; i < n - 1; i++) { cin >> a >> b; graf[a].pb(b); graf[b].pb(a); } ojc[1] = 0; gl[1] = 0; ilegl[0] = {1}; dfs(1); int pocz = 0, kon = 1e9, sr; while (pocz < kon) { sr = (pocz + kon) / 2; //cout << "poczatek i koniec " << pocz << " " << sr << " " << kon << " " << czy(sr) << endl; if (czy(sr)) kon = sr; else pocz = sr + 1; } cout << pocz; }