//#define _GLIBCXX_DEBUG #include "bits/stdc++.h" using namespace std; //------------------------------- Libraries --------------------------------// //------------------------------- Type Names -------------------------------// using i64 = int_fast64_t; using seika = string; //akari : 1D, yukari : 2D, maki : 3D vector template using akari = vector; template using yukari = akari>; template using maki = akari>; //akane : ascending order, aoi : decending order template using akane = priority_queue, greater>; template using aoi = priority_queue; //------------------------------- Dubug Functions ---------------------------// inline void print() { cout << endl; } template void print(const First &first, const Rest &... rest) { cout << first << ' '; print(rest...); } //------------------------------- Solver ------------------------------------// void solve() { int n; cin >> n; yukari g(n); for (int i = 0; i < n - 1; i++) { int u, v; cin >> u >> v; u--, v--; g[u].push_back(v); g[v].push_back(u); } yukari dp(2, akari(n)); auto dfs = [&](auto &&dfs, int v = 0, int p = -1) -> void { dp[0][v] = 1; for (int nv : g[v]) { if (nv == p) { continue; } dfs(dfs, nv, v); dp[1][v] += max(dp[1][nv], dp[0][nv]); dp[0][v] += max(dp[1][nv], dp[0][nv] - 1); } }; dfs(dfs); cout << max(dp[0][0], dp[1][0]) << endl; } int main() { solve(); return 0; }