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

• 問題: No.3769 Even Contraction
• ユーザー: marc2825
• 提出日時: 2026-10-05 10:46:39
• 言語: C++17 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 56 ms / 2,000 ms
• コード長: 5,085 bytes
• コンパイル時間: 1,863 ms
• コンパイル使用メモリ: 241,172 KB
• 実行使用メモリ: 25,304 KB
• 最終ジャッジ日時: 2026-10-16 20:57:29
• 合計ジャッジ時間: 6,772 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge1_0

ファイルパターン	結果
sample	AC * 3
other	AC * 47

ソースコード

/// GPT 5.6 Sol

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

using ll = long long;
const ll NEG = -(1LL << 60);

struct DSU {
    vector<int> p, sz;
    DSU(int n): p(n), sz(n,1) {
        iota(p.begin(), p.end(), 0);
    }
    int find(int x) {
        if (p[x] == x) return x;
        return p[x] = find(p[x]);
    }
    void unite(int a, int b) {
        a = find(a);
        b = find(b);
        if (a == b) return;
        if (sz[a] < sz[b]) swap(a,b);
        p[b] = a;
        sz[a] += sz[b];
    }
};

struct Edge {
    int to;
    int here;   // この成分側の元頂点
    int there;  // 相手成分側の元頂点
    bool trigger; // 0-2 辺か
};

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

    int N;
    cin >> N;

    vector<pair<int,int>> es(N-1);
    for (auto &[u,v] : es) {
        cin >> u >> v;
        --u; --v;
    }

    vector<int> A(N);
    for (int &x : A) cin >> x;

    DSU dsu(N);

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

    vector<int> id(N,-1);
    unordered_map<int,int> mp;
    vector<int> label;

    for (int i=0;i<N;i++) {
        int r = dsu.find(i);

        if (!mp.count(r)) {
            int k = mp.size();
            mp[r] = k;
            label.push_back(A[i]);
        }

        id[i] = mp[r];
    }

    int K = label.size();

    vector<vector<Edge>> G(K);

    for (auto [u,v] : es) {
        int a = id[u];
        int b = id[v];

        if (a == b) continue;

        bool trigger =
            (A[u] == 0 && A[v] == 2) ||
            (A[u] == 2 && A[v] == 0);

        G[a].push_back({b,u,v,trigger});
        G[b].push_back({a,v,u,trigger});
    }

    vector<int> par(K,-1);
    vector<int> parAttach(K,-1);
    vector<bool> parTrigger(K,false);

    vector<int> order = {0};
    par[0] = -2;

    for (int i=0;i<(int)order.size();i++) {
        int v = order[i];

        for (auto e : G[v]) {
            if (par[e.to] != -1) continue;

            par[e.to] = v;
            parAttach[e.to] = e.there;
            parTrigger[e.to] = e.trigger;

            order.push_back(e.to);
        }
    }

    // dp[v][parentTrigger][active]
    vector<array<array<ll,2>,2>> dp(K);

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

    for (int oi=K-1;oi>=0;oi--) {
        int v = order[oi];

        vector<Edge> children;
        for (auto e : G[v]) {
            if (par[e.to] == v)
                children.push_back(e);
        }

        // label 1 は常に active
        if (label[v] == 1) {
            ll val = 0;

            for (auto e : children) {
                int c = e.to;

                val += max(
                    dp[c][0][0],
                    dp[c][0][1] + 1
                );
            }

            dp[v][0][1] = val;
            continue;
        }

        // -------------------------
        // inactive
        // -------------------------
        {
            ll val = 0;

            for (auto e : children) {
                int c = e.to;
                val += max(dp[c][0][0],
                           dp[c][0][1]);
            }

            dp[v][0][0] = val;
        }

        // active のとき、
        // まず全子辺を「発火辺にしない」とした baseline
        ll base = 0;

        // 元頂点 -> その頂点から発火させる場合の最大 delta
        unordered_map<int,ll> bestDelta;

        for (auto e : children) {
            int c = e.to;

            ll U = max(
                dp[c][0][0],
                dp[c][0][1] + 1
            );

            base += U;

            if (e.trigger) {
                ll S = dp[c][1][1] + 1;
                ll delta = S - U;

                auto it = bestDelta.find(e.here);
                if (it == bestDelta.end())
                    bestDelta[e.here] = delta;
                else
                    it->second = max(it->second, delta);
            }
        }

        // -------------------------
        // 親発火なしで active
        // -> 子発火を少なくとも1本使う
        // -------------------------
        {
            ll g0 = 0;
            ll g1 = NEG;

            for (auto [x,d] : bestDelta) {
                ll ng0 = g0;

                ll ng1 = max(
                    g1 + max(0LL,d),
                    g0 + d
                );

                g0 = ng0;
                g1 = ng1;
            }

            if (g1 > NEG/2)
                dp[v][0][1] = base + g1;
        }

        // -------------------------
        // 親発火あり
        // -------------------------
        if (v != 0 && parTrigger[v]) {
            int blocked = parAttach[v];

            ll gain = 0;

            for (auto [x,d] : bestDelta) {
                if (x == blocked) continue;
                gain += max(0LL,d);
            }

            dp[v][1][1] = base + gain;
        }
    }

    ll add = max(dp[0][0][0],
                 dp[0][0][1]);

    cout << (N-K) + add << '\n';
}