#include using namespace std; #define ll long long #define rep(i,n) for(int i=0;i #define all(v) v.begin(),v.end() #define riano_ std::ios::sync_with_stdio(false);std::cin.tie(nullptr) using Graph = vector>; //segment tree //1-indexed class segtree { public: ll n; vector A; segtree(ll k){ n = 1; while(n(2*n,0); } //a[i]をxにする void replace(ll i,ll x){ int index = n-1+i; A[index] = x; while(index>1){ index /= 2; A[index] = max(A[2*index],A[2*index+1]); } } //i-jまでの最大値を求める ll mx(ll i,ll j){ return rangemx(i,j,1,1,n); } // a,b求める区間 k区間番号 c,d区間の始終点(k=1,c=1,d=nで入力する) ll rangemx(ll a,ll b,ll k,ll c,ll d){ //単位元の設定 ll el = 0; if(d vis; int t; vector euler_time; void dfs(Graph &G, int s,int i){ t++; ll st = t; for(int nx:G[s]){ if(vis[nx]==i) continue; vis[nx] = i; dfs(G,nx,i); } t++; ll en = t; euler_time[s] = make_pair(st,en); } void dfs_dp(Graph &G, int s,int i){ for(int nx:G[s]){ if(vis[nx]==i) continue; vis[nx] = i; dfs_dp(G,nx,i); } auto[st,en] = euler_time[s]; //最大から2つ取得 ll m1 = dp.mx(st,en); ll m1_val = m1/base; ll m1_idx = m1%base; dp.replace(m1_idx,0); ll m2 = dp.mx(st,en); ll m2_val = m2/base; ll m2_idx = m2%base; dp.replace(m2_idx,0); //両方正の偶数の場合の処理 if(m1_val%2==0&&m2_val>0&&m2_val%2==0){ m2_val--; dp.replace(m2_idx,base+m2_idx); } //この頂点の行きがけ順番号(st)に値を格納 dp.replace(st,(m1_val+m2_val+1)*base+st); } int main() { riano_; ll ans = 0; ll N; cin >> N; Graph G(N+1); rep(i,N-1){ ll a,b; cin >> a >> b; G[a].push_back(b); G[b].push_back(a); } vis.assign(N+1,-1); euler_time.assign(N+1,make_pair(0,0)); //1を始点としてdfs(euler tour順の番号を求める) vis[1] = 0; t = 0; dfs(G,1,0); //dfs順にdp操作を行う vis[1] = 1; dfs_dp(G,1,1); ans = dp.mx(1,2*N)/base; cout << ans << endl; }