// 制約チェック #line 2 "lib/prelude.hpp" #ifndef LOCAL #pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2") #endif #include using namespace std; using ll = long long; #define rep2(i, m, n) for (auto i = (m); i < (n); i++) #define rep(i, n) rep2(i, 0, n) #define repr2(i, m, n) for (auto i = (n); i-- > (m);) #define repr(i, n) repr2(i, 0, n) #define all(x) begin(x), end(x) #line 3 "lib/ds/dsu.hpp" class dsu { public: dsu(int n) : par(n, -1), count_(n) {} int size() const { return par.size(); } int count() const { return count_; } void clear() { fill(par.begin(), par.end(), -1); count_ = size(); } int find(int x) { return par[x] < 0 ? x : par[x] = (int)find(par[x]); } bool same(int x, int y) { return find(x) == find(y); } bool unite(int x, int y) { x = find(x), y = find(y); if (x == y) return false; if (par[x] > par[y]) swap(x, y); par[x] += par[y], par[y] = (int)x; count_--; return true; } vector> groups() { vector> res(size()); for (int x = 0; x < size(); x++) res[find(x)].push_back(x); res.erase(remove_if(all(res), [](const auto& v) { return v.empty(); }), res.end()); return res; } private: vector par; int count_; }; #line 3 "main.cpp" const int MaxN = 100000; int n; vector G[MaxN]; // paths[v] = {(v-u-で始まる最長パス長, u)} 降順 vector> paths[MaxN]; // longest[v] = {(uの部分木内の最長パス長, u)} 降順 vector> longest[MaxN]; int ans; void dfs1(int v, int p) { for (auto u : G[v]) if (u != p) { dfs1(u, v); paths[v].emplace_back(paths[u][0].first + 1, u); longest[v].emplace_back( max(longest[u][0].first, paths[u][0].first + paths[u][1].first), u); } paths[v].emplace_back(0, -1); paths[v].emplace_back(0, -1); sort(paths[v].begin(), paths[v].end(), greater{}); paths[v].resize(3); longest[v].emplace_back(0, -1); sort(longest[v].begin(), longest[v].end(), greater{}); longest[v].resize(2); } void dfs2(int v, int p) { for (auto u : G[v]) if (u != p) { // 辺{u,v}を消す int u_len = max(longest[u][0].first, paths[u][0].first + paths[u][1].first); int i1 = u == paths[v][0].second ? 1 : 0; int i2 = u == paths[v][i1 + 1].second ? i1 + 2 : i1 + 1; int j = u == longest[v][0].second ? 1 : 0; int v_len = max(longest[v][j].first, paths[v][i1].first + paths[v][i2].first); ans = min(ans, max({u_len, v_len, (u_len + 1) / 2 + (v_len + 1) / 2 + 1})); pair val1(-1, -1), val2(-1, -1); auto it1 = find_if(all(paths[v]), [&](auto&& a) { return a.second == u; }); if (it1 != paths[v].end()) val1 = *it1, paths[v].erase(it1); auto it2 = find_if(all(longest[v]), [&](auto&& a) { return a.second == u; }); if (it2 != longest[v].end()) val2 = *it2, longest[v].erase(it2); paths[u].emplace_back(paths[v][0].first + 1, v); longest[u].emplace_back( max(longest[v][0].first, paths[v][0].first + paths[v][1].first), v); sort(paths[u].begin(), paths[u].end(), greater{}); sort(longest[u].begin(), longest[u].end(), greater{}); dfs2(u, v); if (val1.first != -1) paths[v].insert(it1, val1); if (val2.first != -1) longest[v].insert(it2, val2); } } int main() { scanf("%d", &n); assert(2 <= n && n <= 100000); dsu dsu(n); rep(_, n-1) { int u, v; scanf("%d%d", &u, &v); assert(1 <= u && u <= n); assert(1 <= v && v <= n); assert(u != v); u--, v--; assert(dsu.unite(u, v)); G[u].push_back(v); G[v].push_back(u); } dfs1(0, -1); ans = INT_MAX; dfs2(0, -1); printf("%d\n", ans); }