#define _USE_MATH_DEFINES #include using namespace std; #define FOR(i,m,n) for(int i=(m);i<(n);++i) #define REP(i,n) FOR(i,0,n) #define ALL(v) (v).begin(),(v).end() using ll = long long; constexpr int INF = 0x3f3f3f3f; constexpr long long LINF = 0x3f3f3f3f3f3f3f3fLL; constexpr double EPS = 1e-8; constexpr int MOD = 1000000007; // constexpr int MOD = 998244353; constexpr int DY4[]{1, 0, -1, 0}, DX4[]{0, -1, 0, 1}; constexpr int DY8[]{1, 1, 0, -1, -1, -1, 0, 1}; constexpr int DX8[]{0, -1, -1, -1, 0, 1, 1, 1}; template inline bool chmax(T& a, U b) { return a < b ? (a = b, true) : false; } template inline bool chmin(T& a, U b) { return a > b ? (a = b, true) : false; } struct IOSetup { IOSetup() { std::cin.tie(nullptr); std::ios_base::sync_with_stdio(false); std::cout << fixed << setprecision(20); } } iosetup; template std::vector rerooting_dp( const std::vector>& graph, const std::vector& def, const E merge, const F f, const G g) { const int n = graph.size(); if (n == 0) return {}; if (n == 1) return {g(def[0], 0)}; std::vector> children(n); const std::function dfs1 = [&graph, &def, merge, f, g, &children, &dfs1]( const int par, const int ver) -> CommutativeSemigroup { children[ver].reserve(graph[ver].size()); CommutativeSemigroup dp = def[ver]; for (const int e : graph[ver]) { if (e == par) { children[ver].emplace_back(); } else { children[ver].emplace_back(f(dfs1(ver, e), ver, e)); dp = merge(dp, children[ver].back()); } } return g(dp, ver); }; dfs1(-1, 0); std::vector dp = def; const std::function dfs2 = [&graph, &def, merge, f, g, &children, &dp, &dfs2]( const int par, const int ver, const CommutativeSemigroup& m) -> void { const int c = graph[ver].size(); for (int i = 0; i < c; ++i) { if (graph[ver][i] == par) { children[ver][i] = f(m, ver, graph[ver][i]); break; } } std::vector left{def[ver]}, right; left.reserve(c); for (int i = 0; i < c - 1; ++i) { left.emplace_back(merge(left[i], children[ver][i])); } dp[ver] = g(merge(left.back(), children[ver].back()), ver); if (c >= 2) { right.reserve(c - 1); right.emplace_back(children[ver].back()); for (int i = c - 2; i > 0; --i) { right.emplace_back(merge(children[ver][i], right[c - 2 - i])); } std::reverse(right.begin(), right.end()); } for (int i = 0; i < c; ++i) { if (graph[ver][i] != par) { dfs2(ver, graph[ver][i], g(i + 1 == c ? left[i] : merge(left[i], right[i]), ver)); } } }; dfs2(-1, 0, CommutativeSemigroup()); return dp; } int main() { int n; cin >> n; vector> graph(n); REP(_, n - 1) { int u, v; cin >> u >> v; --u; --v; graph[u].emplace_back(v); graph[v].emplace_back(u); } vector>> children(n), diameter(n); auto f = [&](auto&& f, int par, int ver) -> void { for (int e : graph[ver]) { if (e == par) continue; f(f, ver, e); if (children[e].empty()) { children[ver].emplace_back(1, e); diameter[ver].emplace_back(0, e); } else { children[ver].emplace_back(children[e].front().first + 1, e); if (children[e].size() == 1) { diameter[ver].emplace_back(max(children[e].front().first, diameter[e].front().first), e); } else if (children[e].size() >= 2) { diameter[ver].emplace_back(max(children[e][0].first + children[e][1].first, diameter[e].front().first), e); } } } sort(ALL(children[ver]), greater>()); sort(ALL(diameter[ver]), greater>()); }; f(f, -1, 0); // cout << "[children]\n"; // REP(i, n) { // cout << i << ':'; // for (const auto [v, e] : children[i]) { // cout << " {" << v << ',' << e << '}'; // } // cout << '\n'; // } // cout << "[diameter]\n"; // REP(i, n) { // cout << i << ':'; // for (const auto [v, e] : diameter[i]) { // cout << " {" << v << ',' << e << '}'; // } // cout << '\n'; // } auto g = [&](auto&& g, int par, int ver, int dp1, int dp2) -> void { if (par != -1) { children[ver].emplace_back(dp1, par); diameter[ver].emplace_back(dp2, par); } sort(ALL(children[ver]), greater>()); sort(ALL(diameter[ver]), greater>()); for (int e : graph[ver]) { if (e == par) continue; int nxt_dp1 = 1; if (children[ver].front().second != e) { nxt_dp1 = children[ver].front().first + 1; } else if (children[ver].size() >= 2) { nxt_dp1 = children[ver][1].first + 1; } int nxt_dp2 = 0; if (children[ver].size() == 2) { if (children[ver].front().second == e) { nxt_dp2 = children[ver][1].first; } else { nxt_dp2 = children[ver].front().first; } } else if (children[ver].size() >= 3) { if (children[ver].front().second == e) { nxt_dp2 = children[ver][1].first + children[ver][2].first; } else if (children[ver][1].second == e) { nxt_dp2 = children[ver].front().first + children[ver][2].first; } else { nxt_dp2 = children[ver].front().first + children[ver][1].first; } } int nxt_dp3 = 0; if (diameter[ver].front().second != e) { nxt_dp3 = diameter[ver].front().first; } else if (diameter[ver].size() >= 2) { nxt_dp3 = diameter[ver][1].first; } g(g, ver, e, nxt_dp1, max(nxt_dp2, nxt_dp3)); } }; g(g, -1, 0, 0, 0); // cout << "[children]\n"; // REP(i, n) { // cout << i << ':'; // for (const auto [v, e] : children[i]) { // cout << " {" << v << ',' << e << '}'; // } // cout << '\n'; // } // cout << "[diameter]\n"; // REP(i, n) { // cout << i << ':'; // for (const auto [v, e] : diameter[i]) { // cout << " {" << v << ',' << e << '}'; // } // cout << '\n'; // } int ans = INF; REP(i, n) { for (int e : graph[i]) { int child_diameter = 0; if (children[e].front().second != i) { child_diameter = children[e].front().first; } else if (diameter[e].size() >= 2) { child_diameter = children[e][1].first; } int root_diameter = 0; if (children[i].size() == 2) { if (children[i].front().second == e) { root_diameter = children[i][1].first; } else { root_diameter = children[i].front().first; } } else if (children[i].size() >= 3) { if (children[i].front().second == e) { root_diameter = children[i][1].first + children[i][2].first; } else if (children[i][1].second == e) { root_diameter = children[i].front().first + children[i][2].first; } else { root_diameter = children[i].front().first + children[i][1].first; } } // cout << i << ": " << root_diameter << ' ' << child_diameter << '\n'; chmin(ans, (root_diameter + 1) / 2 + (child_diameter + 1) / 2 + 1); } } cout << ans << '\n'; return 0; }