#include #define all(x) begin(x), end(x) #define times(x) for (int _ = 0 ; _ < (int)(x) ; _++) using i32 = int; using i64 = long long; using ld = long double; using usize = std::size_t; template inline bool chmax(T1 &a, const T2 &b) { return a < b and (a = b, true); } template inline bool chmin(T1 &a, const T2 &b) { return a > b and (a = b, true); } constexpr i64 supl = (std::numeric_limits::max() >> 1) - 100; constexpr i32 supi = (std::numeric_limits::max() >> 1) - 100; namespace zawa::input { template void in(T& res) { std::cin >> res; } template void in(Head& head, Tail&... tail) { in(head); in(tail...); } template void in(std::pair& res) { in(res.first); in(res.second); } template void in(std::vector& res) { for (auto& r : res) { in(r); } } } // namespace zawa::input using zawa::input::in; namespace zawa::output { void out() { std::cout << std::endl; } template void out(const T& a) { std::cout << a << std::endl; } template void out(const std::vector& as) { for (std::size_t i = 0 ; i < as.size() ; i++) { std::cout << as[i] << (i + 1 == as.size() ? '\n' : ' '); } } template void out(const Head& head, const Tail&... tail) { std::cout << head; if (sizeof...(tail)) { std::cout << ' '; } out(tail...); } void yesno(bool flag, std::string yes = "Yes", std::string no = "No") { std::cout << (flag ? yes : no) << std::endl; } } // namespace zawa::output using zawa::output::out; using zawa::output::yesno; // #include "atcoder/modint" // using mint = atcoder::modint998244353; // using mint = atcoder::modint1000000007; // #include "src/template/accum1d.hpp" // #include "src/template/binary-search.hpp" // #include "src/template/binary-search-ld.hpp" // #include "src/algorithm/compression.hpp" // #include "src/algorithm/RLE.hpp" namespace zawa { std::vector> read_graph(int n, int m, bool undirect = true, bool minus = true) { std::vector> res(n, std::vector(0, 0)); for (int _ = 0 ; _ < m ; _++) { int u, v; std::cin >> u >> v; res[u - minus].emplace_back(v - minus); if (undirect) { res[v - minus].emplace_back(u - minus); } } return res; } std::vector> read_tree(int n, bool undirect = true, bool minus = true) { return read_graph(n, n - 1, undirect, minus); } } // #include "src/graph/Read-Weighted-Graph.hpp" using namespace std; void main_() { i32 n; in(n); auto G = zawa::read_tree(n); vector dp(n, vector(2, 0)); auto rec = [&](auto rec, i32 v, i32 p) -> void { for (usize i = 0 ; i < G[v].size() ; i++) { if (G[v][i] == p) { G[v].erase(G[v].begin() + i); break; } } for (auto x : G[v]) { rec(rec, x, v); } dp[v][0] = 0; for (auto x : G[v]) { dp[v][0] += max(dp[x][0], dp[x][1]); } dp[v][1] = 1; for (auto x : G[v]) { dp[v][1] += max(dp[x][0], dp[x][1] - 1); } }; rec(rec, 0, -1); out(*max_element(all(dp[0]))); } i32 main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout << fixed << setprecision(10); main_(); return 0; }