#include using namespace std; #define repd(i,a,b) for (ll i=(a);i<(b);i++) #define rep(i,n) repd(i,0,n) #define all(x) (x).begin(),(x).end() template inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; } template inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; } typedef long long ll; typedef pair P; typedef vector vec; using Graph = vector>; const long long INF = 1LL<<60; const long long MOD = 1000000007; //https://nyaannyaan.github.io/library/graph/graph-template.hpp template struct edge { int src, to; T cost; edge(int _to, T _cost) : src(-1), to(_to), cost(_cost) {} edge(int _src, int _to, T _cost) : src(_src), to(_to), cost(_cost) {} edge &operator=(const int &x) { to = x; return *this; } operator int() const { return to; } }; template using Edges = vector>; template using WeightedGraph = vector>; using UnweightedGraph = vector>; // Input of (Unweighted) Graph UnweightedGraph graph(int N, int M = -1, bool is_directed = false, bool is_1origin = true) { UnweightedGraph g(N); if (M == -1) M = N - 1; for (int _ = 0; _ < M; _++) { int x, y; cin >> x >> y; if (is_1origin) x--, y--; g[x].push_back(y); if (!is_directed) g[y].push_back(x); } return g; } // Input of Weighted Graph template WeightedGraph wgraph(int N, int M = -1, bool is_directed = false, bool is_1origin = true) { WeightedGraph g(N); if (M == -1) M = N - 1; for (int _ = 0; _ < M; _++) { int x, y; cin >> x >> y; T c; cin >> c; if (is_1origin) x--, y--; g[x].emplace_back(x, y, c); if (!is_directed) g[y].emplace_back(y, x, c); } return g; } // Input of Edges template Edges esgraph(int N, int M, int is_weighted = true, bool is_1origin = true) { Edges es; for (int _ = 0; _ < M; _++) { int x, y; cin >> x >> y; T c; if (is_weighted) cin >> c; else c = 1; if (is_1origin) x--, y--; es.emplace_back(x, y, c); } return es; } // Input of Adjacency Matrix template vector> adjgraph(int N, int M, T INF, int is_weighted = true, bool is_directed = false, bool is_1origin = true) { vector> d(N, vector(N, INF)); for (int _ = 0; _ < M; _++) { int x, y; cin >> x >> y; T c; if (is_weighted) cin >> c; else c = 1; if (is_1origin) x--, y--; d[x][y] = c; if (!is_directed) d[y][x] = c; } return d; } /** * @brief グラフテンプレート * @docs docs/graph/graph-template.md */ //https://nyaannyaan.github.io/library/tree/rerooting.hpp // Rerooting // f1(c1, c2) ... merge value of child node // f2(memo[i], chd, par) ... return value from child node to parent node // memo[i] ... result of subtree rooted i // dp[i] ... result of tree rooted i template struct Rerooting { const G &g; const F1 f1; const F2 f2; vector memo, dp; T I; Rerooting(const G &_g, const F1 _f1, const F2 _f2, const T &I_) : g(_g), f1(_f1), f2(_f2), memo(g.size(), I_), dp(g.size(), I_), I(I_) { dfs(0, -1); efs(0, -1, I); } const T &operator[](int i) const { return dp[i]; } void dfs(int cur, int par) { for (auto &dst : g[cur]) { if (dst == par) continue; dfs(dst, cur); memo[cur] = f1(memo[cur], f2(memo[dst], dst, cur)); } } void efs(int cur, int par, const T &pval) { // get cumulative sum vector buf; for (auto dst : g[cur]) { if (dst == par) continue; buf.push_back(f2(memo[dst], dst, cur)); } vector head(buf.size() + 1), tail(buf.size() + 1); head[0] = tail[buf.size()] = I; for (int i = 0; i < (int)buf.size(); i++) head[i + 1] = f1(head[i], buf[i]); for (int i = (int)buf.size() - 1; i >= 0; i--) tail[i] = f1(tail[i + 1], buf[i]); // update dp[cur] = par == -1 ? head.back() : f1(pval, head.back()); // propagate int idx = 0; for (auto &dst : g[cur]) { if (dst == par) continue; efs(dst, cur, f2(f1(pval, f1(head[idx], tail[idx + 1])), cur, dst)); idx++; } } }; /** * @brief Rerooting(全方位木DP) * @docs docs/tree/rerooting.md */ // auto mod int // https://youtu.be/L8grWxBlIZ4?t=9858 // https://youtu.be/ERZuLAxZffQ?t=4807 : optimize // https://youtu.be/8uowVvQ_-Mo?t=1329 : division const int mod = 1000000007; struct mint { ll x; // typedef long long ll; mint(ll x=0):x((x%mod+mod)%mod){} mint operator-() const { return mint(-x);} mint& operator+=(const mint a) { if ((x += a.x) >= mod) x -= mod; return *this; } mint& operator-=(const mint a) { if ((x += mod-a.x) >= mod) x -= mod; return *this; } mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this;} mint operator+(const mint a) const { return mint(*this) += a;} mint operator-(const mint a) const { return mint(*this) -= a;} mint operator*(const mint a) const { return mint(*this) *= a;} mint pow(ll t) const { if (!t) return 1; mint a = pow(t>>1); a *= a; if (t&1) a *= *this; return a; } // for prime mod mint inv() const { return pow(mod-2);} mint& operator/=(const mint a) { return *this *= a.inv();} mint operator/(const mint a) const { return mint(*this) /= a;} }; istream& operator>>(istream& is, mint& a) { return is >> a.x;} ostream& operator<<(ostream& os, const mint& a) { return os << a.x;} using F=tuple; int main() { ios::sync_with_stdio(false); cin.tie(0); ll n; cin>>n; auto g=graph(n,n-1,0,1); auto f1=[&](F x,F y){ auto[a,b,c]=x; auto[A,B,C]=y; chmax(a,A); if(b>B)chmax(c,B); else { c=max(b,C); b=B; } return F(a,b,c); }; map mp; auto f2=[&](F x,ll ch,ll pa){ auto[a,b,c]=x; chmax(a,b+c); mp[{ch,pa}]=a; b++; if(c>=1)c++; return F(a,b,c); }; ll ans=INF; Rerooting dp(g,f1,f2,F(0,0,0)); rep(i,n){ for(ll ni:g[i]){ if(i>ni)continue; ll x=mp[{i,ni}]; ll y=mp[{ni,i}]; ll now=0; chmax(now,x); chmax(now,y); chmax(now,(x+1)/2+(y+1)/2+1); chmin(ans,now); } } cout<