#include #include #define rep(i, n) for (int i = 0; i < (int)(n); i++) using namespace atcoder; using ll = long long; const ll MOD1 = 1000000007LL; const ll MOD2 = 998244353LL; using namespace std; const vector> dpos4 = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}}; // const vector> dpos8 = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}}; template bool chmax(T &a, const T &b) { if (a < b) { a = b; // aをbで更新 return true; } return false; } template bool chmin(T &a, const T &b) { if (a > b) { a = b; // aをbで更新 return true; } return false; } int main() { int N; cin >> N; vector> edges(N); rep(i, N - 1){ int u, v; cin >> u >> v; u--, v--; edges[u].push_back(v); edges[v].push_back(u); } vector> dp(N, vector(2, 0)); auto dfs = [&](auto self, int fr, int prev = -1) -> void { dp[fr][0] = 0; dp[fr][1] = 1; for(auto to: edges[fr]){ if(to == prev) continue; self(self, to, fr); dp[fr][0] += max(dp[to][0], dp[to][1]); dp[fr][1] += max(dp[to][0], dp[to][1] - 1); } }; dfs(dfs, 0); cout << max(dp[0][0], dp[0][1]) << endl; return 0; }