結果

問題 No.763 Noelちゃんと木遊び
コンテスト
ユーザー cutmdo
提出日時 2023-06-14 03:47:43
言語 C++17
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 109 ms / 2,000 ms
コード長 3,087 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,182 ms
コンパイル使用メモリ 90,116 KB
実行使用メモリ 11,648 KB
最終ジャッジ日時 2025-03-22 10:42:36
合計ジャッジ時間 3,520 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#define PROBLEM "https://yukicoder.me/problems/no/763"

#include <iostream>
#include <vector>
#include <queue>

using ll = long long;
using std::cout;
using std::cin;
constexpr char endl = '\n';

template<class Node = int, class Cost = long long>
class Graph {
    //using Node = int;
    //using Cost = long long;
    using Edge = std::pair<Node, Cost>;
    using Edges = std::vector<Edge>;

    const int m_n;
    std::vector<Edges> 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<std::pair<Node, Edge>> 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<std::pair<Node, Node>> 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<Node, Cost>(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<class Node, class Cost, class Lambda>
auto treeDP(const Graph<Node, Cost>& tree, Node root, const Lambda& lambda) {
    auto n = tree.size();
    std::vector<Node> in(n);
    for(const auto& [f, t] : tree.getEdgesAll2()) if(f < t) {
        ++in[f]; ++in[t];
    }
    std::queue<Node> q;
    std::vector<bool> 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<int, bool> tree(n);
    for(int f = 0; f < n - 1; ++f) {
        int u, v;
        cin >> u >> v;
        --u; --v;
        tree.addEdgeUndirected(u, v);
    }

    std::vector<int> dp1(n);
    std::vector<int> 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;
}
0