#include #define rep(i, n) for (int i = 0; i < (n); ++i) #define sz(x) int(x.size()) using namespace std; typedef long long ll; // const int INF = 1e8; const ll INF = 1LL << 60; typedef pair P; ll N; vector> G; ll dp[10010][2]; // dp[v][erase] // erase 0: 消さない 1: 消す void dfs(ll v, ll par = -1) { dp[v][0] = 1; dp[v][1] = 0; for (ll i = 0; i < G[v].size(); i++) { ll next = G[v][i]; if (next != par) { dfs(next, v); // 消さない dp[v][0] += max(dp[next][0] - 1, dp[next][1]); // 消す dp[v][1] += max(dp[next][0], dp[next][1]); } } } int main() { cin >> N; G.resize(N); rep(i, N - 1) { ll u, v; cin >> u >> v; u--; v--; G[u].push_back(v); G[v].push_back(u); } dfs(0); cout << max(dp[0][0], dp[0][1]) << endl; }