#include #include using namespace std; const int MAX_N = 100000; int N; vector table[MAX_N]; int dp1[MAX_N]; // iをwhiteにするとき, 部分木iで黒は最大いくつ塗れるか int dp2[MAX_N]; // iをblackにするとき, 部分木iでは黒は最大いくつ塗れるか // 黒は連続して塗らない. // 葉以外に塗られた黒の個数の最大値 void dfs(int node, int par) { int s1 = 0; int s2 = 1; for (int next : table[node]) { if (node == par) continue; dfs(next, node); s1 += max(dp1[next], dp2[next]); s2 += dp1[next]; } dp1[node] = s1; dp2[node] = s2; } int main() { int N; cin >> N; for (int i = 0; i < N - 1; i++) { int s, t; cin >> s >> t; s--; t--; table[s].push_back(t); table[t].push_back(s); } dfs(0, -1); cout << max(dp1[0], dp2[0]) << endl; }