結果

問題 No.3769 Even Contraction
コンテスト
ユーザー apricity
提出日時 2026-09-22 06:49:33
言語 C++23
(gcc 15.3.0 + boost 1.92.0 + ACL)
コンパイル:
g++-15 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 103 ms / 2,000 ms
+ 4µs
コード長 2,704 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,190 ms
コンパイル使用メモリ 173,168 KB
実行使用メモリ 26,368 KB
最終ジャッジ日時 2026-10-16 20:55:14
合計ジャッジ時間 8,011 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge3_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 47
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <iostream>
#include <vector>
#include <array>
using namespace std;

template<class T, class S>
inline bool chmin(T &a, const S &b) { return (a > b ? a = b, true : false); }

constexpr int INF = 1e9;

int main() {
    int n; cin >> n;
    vector<vector<int>> g(n);
    for (int i = 0; i < n - 1; i++) {
        int u, v; cin >> u >> v; u--; v--;
        g[u].emplace_back(v);
        g[v].emplace_back(u);
    }
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    vector<array<int, 4>> dp(n);
    // 0: contract to A_v (0 or 2)
    // 1: contract to 1, root is uncovered / root can be used in matching
    // 2: contract to 1, root is covered / root can be used in matching
    // 3: contract to 1, root is covered / root cannot be used in matching

    auto rec = [&] (this auto self, int u, int p) -> void {
        array<int, 4> cur;
        cur.fill(INF);
        if (a[u] == 1) cur[3] = 0;
        else cur[0] = cur[1] = 0;

        for (int v : g[u]) if (v != p) {
            self(v, u);
            array<int, 4> nxt;
            nxt.fill(INF);

            // cut u-v
            int mn = INF;
            for (int i : {0, 2, 3}) chmin(mn, dp[v][i] + 1);
            for (int i = 0; i < 4; i++) chmin(nxt[i], cur[i] + mn);

            auto calc = [&](int s_u, int s_v, int s_nxt) { chmin(nxt[s_nxt], cur[s_u] + dp[v][s_v]); };

            // preserve u-v
            if (a[u] == 1 and a[v] == 1) { // 1-1
                calc(3, 3, 3);
            }
            else if (a[u] == 1) { // 1-(0,2)
                calc(3, 3, 3);
                calc(3, 2, 3);
            }
            else if (a[v] == 1) { // (0,2)-1
                calc(0, 3, 1);
                calc(1, 3, 1);
                calc(2, 3, 2);
                calc(3, 3, 3);
            }
            else if (a[u] == a[v]) { // 0-0 or 2-2
                calc(0, 0, 0);
                for (int i : {0, 1}) for (int j : {0, 1}) calc(i, j, 1);
                for (int i : {0, 1}) for (int j : {2, 3}) calc(i, j, 2);
                for (int i : {2, 3}) for (int j : {0, 1, 2, 3}) calc(i, j, i);
            }
            else { // 0-2 or 2-0
                // no match
                for (int i : {0, 1, 2, 3}) for (int j : {2,3}) {
                    int k = (i == 0 ? 1 : i);
                    calc(i, j, k);
                }
                // match
                for (int i : {0, 1, 2}) for (int j : {0, 1, 2}) {
                    calc(i, j, 3);
                }
            }
            swap(cur, nxt);
        }
        dp[u] = cur;
    };

    rec(0, -1);
    int cuts = n;
    for (int i : {0, 2, 3}) chmin(cuts, dp[0][i]);
    int ans = n - 1 - cuts;
    cout << ans << "\n";
}
0