#include "bits/stdc++.h" #include #define rep(i,n) for(int i = 0; i < n; i++) typedef long long ll; typedef unsigned long long ull; using namespace std; #define vll vector> #define vl vector #define vi vector #define vii vector> #define pb push_back #define pf push_front #define ld long double #define Sort(a) sort(a.begin(),a.end()) #define cSort(a,cmp) sort(a.begin(),a.end(),cmp) #define reSort(a) sort(a.rbegin(), a.rend()) static const ll llMAX = numeric_limits::max(); static const int intMAX = numeric_limits::max(); static const ll llMIN = numeric_limits::min(); static const int intMIN = numeric_limits::min(); static const ll d_5 = 100000; static const ll d9_7 = 1000000007; static const ll d_9 = 1000000000; static const double PI=3.14159265358979323846; template void Printvector(std::vector a){ int size = a.size(); rep(i,size){ cout< void Printvector(std::vector> a){ int size = a.size(); rep(i,size){ int size2=a[i].size(); rep(j,size2){ cout< prime_factor(int64_t n) { unordered_map ret; for(int64_t i = 2; i * i <= n; i++) { while(n % i == 0) { ret[i]++; n /= i; } } if(n != 1) ret[n] = 1; return ret; } template vector getaccum(vector a){ int size=a.size(); vector ans(size); ans[0]=a[0]; for(int i=0;i accum,int l,int r){//閉区間[l,r]の総和 if(l==0){ return accum[r]; }else{ return accum[r]-accum[l-1]; } } //グラフ struct edge{ int to; ll length; int num; int pair; }; struct treev{ int num; vector nexts; }; vector vs; vector es; int cmax=0; void createtreenode(int num){//引数は頂点の数 vs=vector(num); /*treev* newt; try{ treev* newt=new treev; } catch (std::bad_alloc&) { // メモリ確保に失敗 // エラー処理 }*/ rep(i,num){ vs[i].num=i; } return ; } void insertree_bidire(ll len,int Va,int Vb,int num){//結ぶ頂点を //双方向 es.pb({Va,len,num,-1}); es.pb({Vb,len,num,-1}); int size=es.size(); es[size-1].pair=size-2; es[size-2].pair=size-1; vs[Va].nexts.push_back(size-1); vs[Vb].nexts.push_back(size-2); return; } void insertree_unidire(ll len,int Va,int Vb,int num){//結ぶ頂点を //単方向,aからbへ es.pb({Vb,len,num,-1}); int size=es.size(); es[size-1].pair=-1; vs[Va].nexts.push_back(size-1); return; } vll dp; void DFS(int root,ll depth,int pre){ //ここにやりたい処理を書く for(auto i:vs[root].nexts){ if(pre==es[i].to){ continue; } DFS(es[i].to,depth+es[i].length,root); } dp[root][1]=1; for(auto i:vs[root].nexts){ if(pre==es[i].to){ continue; } dp[root][0]+=max(dp[i][0],dp[i][1]); dp[root][1]+=max(dp[i][0],dp[i][1]-1); } return; } struct datas{ ll p; ll q; };/* bool cmp(const datas &a, const datas &b) { return a.num < b.num; }*/ template T gcd(T a,T b){ if(a==0){ return b; }else if(b==0){ return a; } while(1) { if(a < b) swap(a, b); if(!b) break; a %= b; } return a; } int main(void){ ll n; cin>>n; createtreenode(n); rep(i,n-1){ int u,v; cin>>u>>v; u--;v--; insertree_bidire(1,u,v,i); } dp=vll(n,vl(2,0)); DFS(0,0,-1); cout<