結果

問題 No.763 Noelちゃんと木遊び
ユーザー cutmdocutmdo
提出日時 2023-06-14 03:47:43
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 95 ms / 2,000 ms
コード長 3,087 bytes
コンパイル時間 2,832 ms
コンパイル使用メモリ 92,460 KB
実行使用メモリ 11,456 KB
最終ジャッジ日時 2023-09-04 18:05:35
合計ジャッジ時間 4,899 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 71 ms
11,428 KB
testcase_01 AC 30 ms
6,084 KB
testcase_02 AC 75 ms
10,032 KB
testcase_03 AC 48 ms
7,820 KB
testcase_04 AC 34 ms
6,744 KB
testcase_05 AC 47 ms
7,496 KB
testcase_06 AC 94 ms
11,456 KB
testcase_07 AC 86 ms
11,084 KB
testcase_08 AC 50 ms
8,000 KB
testcase_09 AC 33 ms
6,568 KB
testcase_10 AC 13 ms
4,376 KB
testcase_11 AC 93 ms
11,436 KB
testcase_12 AC 80 ms
10,720 KB
testcase_13 AC 79 ms
10,452 KB
testcase_14 AC 72 ms
9,588 KB
testcase_15 AC 48 ms
7,924 KB
testcase_16 AC 8 ms
4,376 KB
testcase_17 AC 47 ms
7,832 KB
testcase_18 AC 95 ms
11,456 KB
testcase_19 AC 80 ms
10,584 KB
testcase_20 AC 81 ms
10,588 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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