#include #include #include #include #include #include #include #include #include #include #include #include #include #define debug_value(x) cerr << "line" << __LINE__ << ":<" << __func__ << ">:" << #x << "=" << x << endl; #define debug(x) cerr << "line" << __LINE__ << ":<" << __func__ << ">:" << x << endl; template inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; } template inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; } using namespace std; typedef long long ll; template vector> vec2d(int n, int m, T v){ return vector>(n, vector(m, v)); } template vector>> vec3d(int n, int m, int k, T v){ return vector>>(n, vector>(m, vector(k, v))); } template void print_vector(vector v, char delimiter=' '){ if(v.empty()) { cout << endl; return; } for(int i = 0; i+1 < v.size(); i++) cout << v[i] << delimiter; cout << v.back() << endl; } vector tree_diameter(vector> g){ int n = g.size(); vector used(n, false); vector dist(n); auto clear = [&](){ for(int i = 0; i < n; i++) used[i] = false; }; auto dfs = [&](auto&& f, int v, int d) -> void{ used[v] = true; dist[v] = d; for(int to : g[v]){ if(!used[to]) f(f, to, d+1); } }; dfs(dfs, 0, 0); int s = 0; for(int i = 0; i < n; i++){ if(dist[s] < dist[i]) s = i; } clear(); dfs(dfs, s, 0); int t = 0; for(int i = 0; i < n; i++){ if(dist[t] < dist[i]) t = i; } int v = t; vector path; path.push_back(t); while(v != s){ for(int to : g[v]){ if(dist[to] == dist[v]-1) { v = to; break; } } path.push_back(v); } return path; } void calc_depth(int v, int par, vector> &g, vector &max_depth, vector &is_in_diameter, int d){ max_depth[v] = d; for(int to: g[v]){ if(to == par) continue; if(is_in_diameter[to]) calc_depth(to, v, g, max_depth, is_in_diameter, d); else { calc_depth(to, v, g, max_depth, is_in_diameter, d+1); chmax(max_depth[v], max_depth[to]); } } } int main(){ ios::sync_with_stdio(false); cin.tie(0); cout << setprecision(10) << fixed; int n; cin >> n; vector> g(n); for(int i = 0; i < n-1; i++){ int u, v; cin >> u >> v; u--; v--; g[u].push_back(v); g[v].push_back(u); } auto diam = tree_diameter(g); vector is_in_diamerer(n); for(int v: diam) is_in_diamerer[v] = true; int s = diam[0], t = diam.back(); vector max_depth_s(n), max_depth_t(n); calc_depth(s, -1, g, max_depth_s, is_in_diamerer, 0); calc_depth(t, -1, g, max_depth_t, is_in_diamerer, 0); assert(max_depth_s == max_depth_t); int r = diam.size()-1; vector lr(r+1), rr(r+1); for(int i = 1; i < r; i++){ int u = diam[i]; lr[i] = max(lr[i-1], max_depth_s[u]+i); } for(int i = r-1; i > 0; i--){ int u = diam[i]; rr[i] = max(rr[i+1], max_depth_t[u]+(r-i)); } // print_vector(lr); // print_vector(rr); int ans = r; for(int i = 0; i < r; i++){ chmin(ans, max({lr[i], rr[i+1], (lr[i]+1)/2+(rr[i+1]+1)/2+1})); // debug_value((lr[i]+1)/2+(rr[i+1]+1)/2+1) } cout << ans << endl; }