#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include template inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; } template inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; } constexpr long long MAX = 5100000; constexpr long long INF = 1LL << 60; constexpr int inf = 1 << 28; //constexpr long long mod = 1000000007LL; //constexpr long long mod = 998244353LL; using namespace std; typedef unsigned long long ull; typedef long long ll; int n; vector> g; vector> dp; void dfs(int cur, int pre) { for (int next : g[cur]) { if (next == pre) continue; dfs(next, cur); } int res1 = 1; int res2 = 0; for (int next : g[cur]) { if (next == pre) continue; res2 += max(dp[next][0], dp[next][1]); res1 += max(dp[next][0] - 1, dp[next][1]); } dp[cur][0] = res1; dp[cur][1] = res2; } int main() { /* cin.tie(nullptr); ios::sync_with_stdio(false); */ scanf("%d", &n); g.resize(n); dp = vector>(n, vector(2)); for (int i = 0; i < n - 1; i++) { int u, v; scanf("%d %d", &u, &v); u--; v--; g[u].push_back(v); g[v].push_back(u); } dfs(0, -1); cout << max(dp[0][0], dp[0][1]) << endl; return 0; /* おまじないを使ったらscanfとprintf関連注意!!!!!!!!!!!! */ }