#include using namespace std; #include using namespace atcoder; using ll=long long; using Graph=vector>; #define INF 1000000000 #define MOD 998244353 #define MAX 300000 int ans=0; priority_queue* dfs(Graph &G,int v,int p,vector &sz){ priority_queue* pq = new priority_queue(); vector*> pqs; for(int nv:G[v]){ if(nv==p){ continue; } pqs.push_back(dfs(G,nv,v,sz)); pq->push(sz[nv]); } if(pq->size()==1){ if(pqs[0]->size()>0){ ans+=pqs[0]->top(); pqs[0]->pop(); } } sz[v]=1; for(int i=0;i<2;i++){ if(pq->empty()){ break; } sz[v]+=pq->top(); pq->pop(); } int best_i=-1; int best_n=pq->size(); for(int i=0;isize()>best_n){ best_i=i; best_n=pqs[i]->size(); } } if(best_i==-1){ for(int i=0;iempty()){ pq->push(pqs[i]->top()); pqs[i]->pop(); } } return pq; }else{ for(int i=0;iempty()){ pqs[best_i]->push(pqs[i]->top()); pqs[i]->pop(); } } while(!pq->empty()){ pqs[best_i]->push(pq->top()); pq->pop(); } return pqs[best_i]; } } int main(){ int N; cin>>N; Graph G(N); for(int i=0;i>x>>y; x--;y--; G[x].push_back(y); G[y].push_back(x); } vector sz(N); dfs(G,0,-1,sz); ans+=sz[0]; cout<