#include using namespace std; typedef long long int ll; typedef pair P; typedef vector VI; typedef vector VVI; #define REP(i,n) for(ll i=0;i<(n);i++) #define ALL(v) v.begin(),v.end() template bool chmax(T &x, const T &y) {return (x bool chmin(T &x, const T &y) {return (x>y)?(x=y,true):false;}; constexpr ll MOD=998244353; constexpr ll INF=2e18; template struct Segtree{ using F=function; int n; F f; X ex; vector dat; Segtree(int n_, F f_, X ex_):f(f_), ex(ex_){ n=1; while(n_>n){n*=2;} dat.assign(2*n,ex); } void set(int i, X x){ dat[i+n-1]=x; } void build(){ for(int k=n-2;k>=0;k--) dat[k]=f(dat[2*k+1],dat[2*k+2]); } void update(int i, X x){ i+=n-1; dat[i]=x; while(i>0){ i=(i-1)/2; dat[i]=f(dat[i*2+1],dat[i*2+2]); } } X query(int a, int b){ return query_sub(a,b,0,0,n); } X query_sub(int a, int b, int k, int l, int r){ if(r<=a||b<=l) return ex; else if(a<=l&&r<=b) return dat[k]; else{ X vl=query_sub(a,b,k*2+1,l,(l+r)/2); X vr=query_sub(a,b,k*2+2,(l+r)/2,r); return f(vl,vr); } } }; P segf(P l, P r){ if(l.first>r.first) return l; else return r; } VI g[210000]; Segtree

seg(420000,segf,{0,0}); VI lidx(210000); VI ridx(210000); int sidx=0; int dfs(int v, int p){ if(g[v].size()==1&&v!=0){ return 1; } VI a; lidx[v]=sidx; sidx++; for(auto to:g[v]){ if(to!=p){ int ret=dfs(to,v); a.push_back(ret); } } ridx[v]=sidx; sidx++; sort(ALL(a),greater()); if(a.size()==1){ P sret=seg.query(lidx[v],ridx[v]); seg.update(sret.second,{0,sret.second}); a.push_back(sret.first); } int j=lidx[v]; for(int i=2;i<(int)a.size();i++){ while(1){ if(seg.query(j,j+1).first==0){ seg.update(j,{a[i],j}); break; } j++; } } return a[0]+a[1]+1; } int main(){ int n; cin >> n; int a, b; REP(i,n-1){ cin >> a >> b; a--, b--; g[a].push_back(b); g[b].push_back(a); } REP(i,420000){ seg.set(i,{0,i}); } cout << dfs(0,-1) << endl; return 0; }