#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; #define rep(a,n) for(ll a = 0;a < n;a++) #define repi(a,b,n) for(ll a = b;a < n;a++) template void chmax(T& reference, T value) { reference = max(reference, value); } template void chmaxmap(map& m, T key, T value) { if (m.count(key)) { chmax(m[key], value); } else { m[key] = value; } } template void chmin(T& reference, T value) { reference = min(reference, value); } struct RollingHash { typedef long long int_type; typedef pair hash_type; int_type base1; int_type base2; int_type mod1; int_type mod2; vector hash1; vector hash2; vector pow1; vector pow2; RollingHash(const string& s) : base1(1009), base2(1007), mod1(1000000007), mod2(1000000009) { init(s); } void init(const string& s) { int n = s.size(); hash1.assign(n + 1, 0); hash2.assign(n + 1, 0); pow1.assign(n + 1, 1); pow2.assign(n + 1, 1); for (int i = 0; i < n; i++) { hash1[i + 1] = (hash1[i] + s[i]) * base1 % mod1; hash2[i + 1] = (hash2[i] + s[i]) * base2 % mod2; pow1[i + 1] = pow1[i] * base1 % mod1; pow2[i + 1] = pow2[i] * base2 % mod2; } } hash_type get(int l, int r) const { int_type t1 = ((hash1[r] - hash1[l] * pow1[r - l]) % mod1 + mod1) % mod1; int_type t2 = ((hash2[r] - hash2[l] * pow2[r - l]) % mod2 + mod2) % mod2; return make_pair(t1, t2); } RollingHash::hash_type concat(hash_type h1, hash_type h2, int h2_len) { return make_pair((h1.first * pow1[h2_len] + h2.first) % mod1, (h1.second * pow2[h2_len] + h2.second) % mod2); } int LCP(const RollingHash& other, int l1, int r1, int l2, int r2) { int len = min(r1 - l1, r2 - l2); int low = -1, high = len + 1; while (high - low > 1) { int mid = (low + high) / 2; if (get(l1, l1 + mid) == other.get(l2, l2 + mid)) low = mid; else high = mid; } return (low); } }; #include using namespace atcoder; typedef modint1000000007 mint; int main() { int n; std::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

grid(n, P{-1,-1}); function dfs = [&](int current, int parent) { if (grid[current].first != -1) { return grid[current]; } vector

cs; for (auto x : g[current]) { if (x == parent) continue; cs.push_back(dfs(x, current)); } int len = cs.size(); if (len == 0) { grid[current] = { 0, 1 }; return grid[current]; } ll p1 = 0, p2 = 0, p3 = 0; for (auto x : cs) { p1 += max(x.first, x.second); } for (auto x : cs) { p2 += max(x.first, x.second); } for (auto x : cs) { p3 += x.first; } p3++; grid[current] = { p1, max(p2, p3) }; return grid[current]; }; auto p = dfs(0, -1); cout << max(p.first, p.second) << endl; return 0; }