#define PROBLEM "https://yukicoder.me/problems/no/763" #include #include #include using ll = long long; using std::cout; using std::cin; constexpr char endl = '\n'; template class Graph { //using Node = int; //using Cost = long long; using Edge = std::pair; using Edges = std::vector; const int m_n; std::vector m_graph; public: Graph(int n) :m_n(n), m_graph(n) {} auto addEdge(const Node& f, const Node& t, const Cost& c = 1) { m_graph[f].emplace_back(t, c); } auto addEdgeUndirected(const Node& f, const Node& t, const Cost& c = 1) { addEdge(f, t, c); addEdge(t, f, c); } auto getEdges(const Node& from)const { class EdgesRange { const typename Edges::const_iterator b, e; public: EdgesRange(const Edges& edges) :b(edges.begin()), e(edges.end()) {} auto begin()const { return b; } auto end()const { return e; } }; return EdgesRange(m_graph[from]); } auto getEdgesAll()const { std::deque> edges; for(Node from = 0; from < m_n; ++from) for(const auto& edge : getEdges(from)) { edges.emplace_back(from, edge); } return edges; } auto getEdgesAll2()const { std::deque> edges; for(Node from = 0; from < m_n; ++from) for(const auto& [to, _] : getEdges(from)) { edges.emplace_back(from, to); } return edges; } auto reverse()const { auto rev = Graph(m_n); for(const auto& [from, edge] : getEdgesAll()) { auto [to, c] = edge; rev.addEdge(to, from, c); } return rev; } auto size()const { return m_n; }; }; template auto treeDP(const Graph& tree, Node root, const Lambda& lambda) { auto n = tree.size(); std::vector in(n); for(const auto& [f, t] : tree.getEdgesAll2()) if(f < t) { ++in[f]; ++in[t]; } std::queue q; std::vector used(n); for(Node i = 0; i < n; ++i)if(i != root && in[i] == 1) { q.emplace(i); } while(!q.empty()) { auto from = q.front(); q.pop(); used[from] = true; for(const auto& [to, _] : tree.getEdges(from)) { if(used[to]) { continue; } lambda(from, to); --in[to]; if(in[to] == 1) { q.emplace(to); } } } } signed main() { ll n; cin >> n; Graph tree(n); for(int f = 0; f < n - 1; ++f) { int u, v; cin >> u >> v; --u; --v; tree.addEdgeUndirected(u, v); } std::vector dp1(n); std::vector dp2(n, 1); treeDP(tree, 0, [&](int f, int t) { dp1[t] += std::max(dp1[f], dp2[f]); dp2[t] += std::max(dp1[f], dp2[f] - 1); }); auto ans = std::max(dp1[0], dp2[0]); cout << ans << endl; }