#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; const ll mod = 1000000007; const ll INF = (ll)1000000007 * 1000000007; typedef pair P; #define rep(i, n) for (int i = 0; i < n; i++) #define per(i, n) for (int i = n - 1; i >= 0; i--) #define Rep(i, sta, n) for (int i = sta; i < n; i++) #define Per(i, sta, n) for (int i = n - 1; i >= sta; i--) typedef long double ld; const ld eps = 1e-8; const ld pi = acos(-1.0); typedef pair LP; int dx[8] = {1, -1, 0, 0, 1, 1, -1, -1}; int dy[8] = {0, 0, 1, -1, 1, -1, 1, -1}; template using max_heap = priority_queue; template using min_heap = priority_queue, greater<>>; template bool chmax(T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; } template bool chmin(T &a, const T &b) { if (b < a) { a = b; return 1; } return 0; } struct edge { int to, id, t; edge() {} edge(int to, int id, int t) : to(to), id(id), t(t) {} }; int n; vector G[200010]; int depth[200010], di[200010][2]; P max_depth[200010][3]; void dfs1(int s, int par, edge pre_e) { if (par != -1) depth[s] = depth[par] + 1; for (edge e : G[s]) { if (e.to == par) continue; dfs1(e.to, s, e); if (max_depth[s][0].first < max_depth[e.to][2].first + 1) { max_depth[s][0] = {max_depth[e.to][2].first + 1, e.id}; sort(max_depth[s], max_depth[s] + 3); } if (pre_e.id != -1) chmax(di[pre_e.id][pre_e.t], di[e.id][e.t]); } if (pre_e.id != -1) chmax(di[pre_e.id][pre_e.t], max_depth[s][2].first + max_depth[s][1].first); } void dfs2(int s, int par, edge pre_e, int depth_par) { multiset

v = { max_depth[s][0], max_depth[s][1], max_depth[s][2], {depth_par, pre_e.id}}; for (edge e : G[s]) { if (e.to == par) continue; P erased = P(-1, -1); for (auto it = v.begin(); it != v.end();) { if ((*it).second == e.id) { erased = *it; it = v.erase(it); } else it++; } auto it = v.end(); it--; int d_first = (*it).first; it--; int d_second = (*it).first; cout << s << " " << e.id << " " << d_first << " " << d_second << endl; for (P t : v) cout << t.first << " " << t.second << endl; dfs2(e.to, s, e, d_first + 1); chmax(di[e.id][1 - e.t], d_first + d_second); if (erased != P(-1, -1)) v.insert(erased); } } void dfs3(int s, int par, edge pre_e) { for (edge e : G[s]) { if (e.to == par) continue; if (par != -1) chmax(di[e.id][1 - e.t], di[pre_e.id][1 - pre_e.t]); dfs3(e.to, s, e); } } void dfs4(int s, int par) { multiset

se; se.insert(P(0, -1)); for (edge e : G[s]) { if (e.to == par) continue; dfs4(e.to, s); se.insert(P(di[e.id][e.t], e.id)); } for (edge e : G[s]) { auto it = se.end(); it--; if ((*it).second == e.id) it--; chmax(di[e.id][1 - e.t], (*it).first); } } void solve() { cin >> n; rep(i, n - 1) { int a, b; cin >> a >> b; a--; b--; G[a].push_back({b, i, 0}); G[b].push_back({a, i, 1}); } rep(i, n) rep(j, 3) max_depth[i][j] = P(0, -1); rep(i, n - 1) rep(j, 2) di[i][j] = -1; dfs1(0, -1, {0, -1, -1}); // rep(i, n) cout << depth[i] << " "; // cout << "" << endl; // rep(i, n) { // rep(j, 3) cout << max_depth[i][j].first << " "; // cout << "" << endl; // } // rep(i, n - 1) { cout << di[i][0] << " " << di[i][1] << endl; } dfs2(0, -1, {0, -1, -1}, 0); dfs3(0, -1, {0, -1, -1}); dfs4(0, -1); rep(i, n - 1) { cout << di[i][0] << " " << di[i][1] << endl; } // rep(i, n - 1) { cout << di[i][0] << " " << di[i][1] << endl; } int ans = mod; rep(i, n - 1) { chmin(ans, max({di[i][0], di[i][1], 1 + (di[i][0] + 1) / 2 + (di[i][1] + 1) / 2})); } cout << ans << endl; } int main() { ios::sync_with_stdio(false); cin.tie(0); cout << fixed << setprecision(50); solve(); }