#1191465 (C++17) No.3769 Even Contraction

• 問題: No.3769 Even Contraction
• ユーザー: marc2825
• 提出日時: 2026-10-04 20:46:33
• 言語: C++17 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: WA
• 実行時間: -
• コード長: 7,849 bytes
• コンパイル時間: 5,400 ms
• コンパイル使用メモリ: 235,644 KB
• 実行使用メモリ: 39,584 KB
• 最終ジャッジ日時: 2026-10-16 20:57:21
• 合計ジャッジ時間: 11,935 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge2_0

ファイルパターン	結果
sample	AC * 3
other	AC * 34 WA * 13

ソースコード

#include <bits/stdc++.h>
using namespace std;

using vi = vector<int>;
using vvi = vector<vi>;

const int INF = 1e9;
const int NEG = -INF;

struct UnionFind {
    vector<int> par, sz;

    UnionFind(int n) : par(n, -1), sz(n, 1) {}

    int root(int x) {
        if (par[x] == -1) return x;
        return par[x] = root(par[x]);
    }

    bool unite(int x, int y) {
        x = root(x);
        y = root(y);

        if (x == y) return false;

        if (sz[x] < sz[y]) swap(x, y);

        par[y] = x;
        sz[x] += sz[y];

        return true;
    }
};

bool is02(int x, int y) {
    return
        (x == 0 && y == 2) ||
        (x == 2 && y == 0);
}

void solve() {
    int N;
    cin >> N;

    vvi G(N);

    vector<pair<int,int>> edges;

    for (int i = 0; i < N - 1; i++) {
        int u, v;
        cin >> u >> v;
        --u;
        --v;

        G[u].push_back(v);
        G[v].push_back(u);

        edges.push_back({u, v});
    }

    vi A(N);

    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }

    // --------------------------------------------------------
    // 同じ値の連結成分を縮約
    // --------------------------------------------------------

    UnionFind uf(N);

    for (auto [u, v] : edges) {
        if (A[u] == A[v]) {
            uf.unite(u, v);
        }
    }

    vi id(N, -1);

    int M = 0;

    for (int v = 0; v < N; v++) {
        if (uf.root(v) == v) {
            id[v] = M++;
        }
    }

    vi cid(N);

    for (int v = 0; v < N; v++) {
        cid[v] = id[uf.root(v)];
    }

    vi val(M);
    vi cap(M, 0);

    for (int v = 0; v < N; v++) {
        int c = cid[v];

        val[c] = A[v];
        cap[c]++;
    }

    vvi T(M);

    for (auto [u, v] : edges) {
        int x = cid[u];
        int y = cid[v];

        if (x == y) continue;

        T[x].push_back(y);
        T[y].push_back(x);
    }

    // --------------------------------------------------------
    //
    // dp[v][p][a]
    //
    // p:
    //   親との 0-2 辺を「起爆辺」として選んでいるか
    //
    // a:
    //   この成分が active (= 最終的に1になる) か
    //
    // 値:
    //   v 以下で縮約できる「成分間の辺」の最大本数
    //
    // ※ 親-v の辺自体は親側で数える
    //
    // --------------------------------------------------------

    vector<array<array<int,2>,2>> dp(M);

    for (int v = 0; v < M; v++) {
        for (int p = 0; p < 2; p++) {
            for (int a = 0; a < 2; a++) {
                dp[v][p][a] = NEG;
            }
        }
    }

    function<void(int,int)> dfs =
        [&](int v, int par) {

        for (int u : T[v]) {
            if (u == par) continue;

            dfs(u, v);
        }

        // 親との起爆辺を使うか
        for (int parent_used = 0; parent_used <= 1; parent_used++) {

            // この成分が active か
            for (int active = 0; active <= 1; active++) {

                // 1成分は最初から active
                if (val[v] == 1) {
                    if (!active) continue;
                    if (parent_used) continue;
                }

                // 0/2成分で親辺を使っているなら active
                if (val[v] != 1) {
                    if (parent_used && !active) continue;
                }

                // 容量不足
                if (parent_used > cap[v]) continue;

                int base = 0;

                vector<int> gain;

                bool ok = true;

                for (int u : T[v]) {
                    if (u == par) continue;

                    // -----------------------------------------
                    // v-u を起爆辺にしない
                    // -----------------------------------------

                    int no_use = NEG;

                    for (int child_active = 0;
                         child_active <= 1;
                         child_active++) {

                        if (dp[u][0][child_active] <= NEG / 2) {
                            continue;
                        }

                        int add =
                            dp[u][0][child_active];

                        // 両端 active ならこの辺も縮約できると仮定
                        if (active && child_active) {
                            add++;
                        }

                        no_use = max(no_use, add);
                    }

                    if (no_use <= NEG / 2) {
                        ok = false;
                        break;
                    }

                    base += no_use;

                    // -----------------------------------------
                    // v-u を 0-2 の起爆辺として使用
                    // -----------------------------------------

                    if (active && is02(val[v], val[u])) {

                        if (dp[u][1][1] > NEG / 2) {

                            int use =
                                dp[u][1][1] + 1;

                            gain.push_back(
                                use - no_use
                            );
                        }
                    }
                }

                if (!ok) continue;

                // ------------------------------------------------
                // 選べる子方向の起爆辺の最大数
                //
                // 嘘ポイント：
                // 「成分サイズ = 独立に使えるport数」
                // と仮定している
                // ------------------------------------------------

                int K = cap[v] - parent_used;

                // activeでないなら、1本も起爆辺を選べない
                if (!active) {
                    if (parent_used) continue;

                    dp[v][0][0] =
                        max(dp[v][0][0], base);

                    continue;
                }

                // value=1 なら起爆辺はそもそも存在しない
                if (val[v] == 1) {
                    dp[v][0][1] =
                        max(dp[v][0][1], base);

                    continue;
                }

                // 0/2で active になるには、
                //
                // 親辺を使っていない場合：
                //   子方向で最低1本必要
                //
                // 親辺を使っている場合：
                //   0本でもよい
                int need =
                    (parent_used ? 0 : 1);

                if ((int)gain.size() < need) continue;
                if (K < need) continue;

                sort(
                    gain.rbegin(),
                    gain.rend()
                );

                int cur = base;

                int used = 0;

                // activeにするため最低1本必要
                while (used < need) {
                    cur += gain[used];
                    used++;
                }

                // あとは得するものだけ選ぶ
                while (
                    used < K &&
                    used < (int)gain.size() &&
                    gain[used] > 0
                ) {
                    cur += gain[used];
                    used++;
                }

                dp[v][parent_used][1] =
                    max(
                        dp[v][parent_used][1],
                        cur
                    );
            }
        }
    };

    dfs(0, -1);

    // 同値成分内部の辺は全部縮約できると仮定
    int inner = N - M;

    int cross =
        max(
            dp[0][0][0],
            dp[0][0][1]
        );

    int ans = inner + cross;

    ans = min(ans, N - 1);

    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    solve();
}