#include #include using namespace std; const int MAX = 110000; int N; vector G[MAX]; int dp[MAX][2]; // 0: v remained, 1: v erased void rec(int v, int p = -1) { dp[v][0] = 1; dp[v][1] = 0; for (auto ch : G[v]) { if (ch == p) continue; rec(ch, v); dp[v][0] += max(dp[ch][0]-1, dp[ch][1]); dp[v][1] += max(dp[ch][0], dp[ch][1]); } //cout << v << ", " << dp[v][0] << ": " << dp[v][1] << endl; } int main() { cin >> 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); } rec(0); cout << max(dp[0][0], dp[0][1]) << endl; }