#include #define M_PI 3.14159265358979323846 // pi using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair P; typedef tuple t3; typedef tuple t4; typedef tuple t5; #define rep(a,n) for(ll a = 0;a < n;a++) template static inline void chmin(T& ref, const T value) { if (ref > value) ref = value; } template static inline void chmax(T& ref, const T value) { if (ref < value) ref = value; } #include using namespace atcoder; typedef modint1000000007 mint; int main() { ll n; cin >> n; vector> g(n); rep(i, n - 1) { int a, b; cin >> a >> b; a--; b--; g[a].push_back(b); g[b].push_back(a); } vector

dp(n, P{ -1,-1 }); function dfs = [&](int current, int parent) { if (dp[current].first != -1) { return dp[current]; } int cs = 0; for (auto x : g[current]) { if (x == parent) continue; cs++;; } if (cs == 0) { dp[current] = P{ 0, 1 }; return dp[current]; } ll cut = 0; for (auto x : g[current]) { if (x == parent) continue; P p = dfs(x, current); cut += max(p.first, p.second); } ll notCut = 1; for (auto x : g[current]) { if (x == parent) continue; P p = dfs(x, current); notCut += max(p.first, p.second - 1); } dp[current] = { cut, notCut }; return dp[current]; }; P v = dfs(0, -1); cout << max(v.first, v.second) << endl; return 0; }