#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; #define FOR(i,a,b) for(ll i=(a);i<(b);++i) #define ALL(v) (v).begin(), (v).end() #define p(s) cout<<(s)< void vprint(T &V){ for(auto v : V){ cout << v << " "; } cout << endl; } const int N_MAX = 100010; vector > G; ll dp[N_MAX][2]; // dp[i][0] : iを削除する場合の最大値 // dp[i][0] : iを削除しない場合の最大値 // dfs(i)を呼ぶと // dp[i][0] // dp[i][1] // が埋まるとする void dfs(ll i, ll parent){ // leaf if(G[i].size()==1 && G[i][0]==parent){ dp[i][0] = 0; dp[i][1] = 1; return; } dp[i][0] = 0; dp[i][1] = 1; for(auto to : G[i]){ if(to==parent) continue; dfs(to, i); dp[i][0] += max(dp[to][0], dp[to][1]); dp[i][1] += max(dp[to][0], dp[to][1]-1); } } int main(){ cin.tie(0); ios::sync_with_stdio(false); // input ll N; cin >> N; G.resize(N); FOR(i, 0, N-1){ ll u, v; cin >> u >> v; u--; v--; G[u].push_back(v); G[v].push_back(u); } dfs(0, -1); ll ans = max(dp[0][0], dp[0][1]); p(ans); return 0; }