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

• 問題: No.3769 Even Contraction
• ユーザー: marc2825
• 提出日時: 2026-10-05 10:53:19
• 言語: C++17 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: WA
• 実行時間: -
• コード長: 5,124 bytes
• コンパイル時間: 855 ms
• コンパイル使用メモリ: 113,148 KB
• 実行使用メモリ: 27,520 KB
• 最終ジャッジ日時: 2026-10-16 20:57:55
• 合計ジャッジ時間: 5,397 ms
• ジャッジサーバーID （参考情報）: judge5_0 / judge1_0

ファイルパターン	結果
sample	AC * 2 WA * 1
other	AC * 30 WA * 17

ソースコード

/// Gemini 3.8 Flash

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>

using namespace std;

const int INF = 1e9;

// 素集合データ構造 (Union-Find)
struct UnionFind {
    vector<int> par, rank;
    UnionFind(int n) : par(n), rank(n, 0) {
        iota(par.begin(), par.end(), 0);
    }
    int find(int x) {
        if (par[x] == x) return x;
        return par[x] = find(par[x]);
    }
    bool unite(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) return false;
        if (rank[x] < rank[y]) swap(x, y);
        par[y] = x;
        if (rank[x] == rank[y]) rank[x]++;
        return true;
    }
};

int N;
vector<int> A;
vector<vector<int>> adj;

// dp_parent[u]: u が親とマッチングする場合の u の部分木の最小コスト
// dp_one[u]   : u は親とマッチングせず、u 自身が「値1の成分」に属し、
//               かつ親も「値1の成分」に属していると仮定したときの最小コスト
// dp_none[u]  : u は親とマッチングせず、u 自身が「値1の成分」に属さないときの最小コスト
vector<int> dp_parent, dp_one, dp_none;

void dfs(int u, int p) {
    int sum_opt_one = 0;
    int sum_opt_none = 0;
    
    // 子頂点に対する DP を先に実行
    vector<int> children;
    for (int v : adj[u]) {
        if (v == p) continue;
        dfs(v, u);
        children.push_back(v);

        // 親 (u) が「値1の成分」に属している場合の子 v の最適コスト
        int opt_v_when_u_one = min(dp_one[v], dp_none[v]);
        sum_opt_one += opt_v_when_u_one;

        // 親 (u) が「値1の成分」に属していない場合の子 v の最適コスト
        // (v が値1の成分になるなら、v が新たな成分の根となるため +1 のコストがかかる)
        int opt_v_when_u_none = min(dp_one[v] + 1, dp_none[v]);
        sum_opt_none += opt_v_when_u_none;
    }

    // 1. dp_none[u] の計算: u 自身が独立して残る (コスト +1)
    if (A[u] == 1) {
        dp_none[u] = INF; // 元々 1 の頂点は「値1の成分」に必ず属する
    } else {
        dp_none[u] = 1 + sum_opt_none;
    }

    // 2. dp_parent[u] の計算: u が親とマッチングする
    if (A[u] == 1) {
        dp_parent[u] = INF; // 1 は 0 や 2 とマッチングできない
    } else {
        // 親とマッチングして 1 になるため、u は「値1の成分」に属し、親と同じ成分になる (追加コスト 0)
        dp_parent[u] = sum_opt_one;
    }

    // 3. dp_one[u] の計算: u は親とはマッチングせず、自身が「値1の成分」になる
    int cost_one = INF;

    // パターン (a): 子とマッチングしない (A[u] == 1 の場合のみ可能)
    if (A[u] == 1) {
        cost_one = min(cost_one, sum_opt_one);
    }

    // パターン (b): ある子 v* とマッチングする (A[u] in {0, 2} の場合)
    if (A[u] != 1) {
        for (int v : children) {
            // マッチング可能な子: 偶奇が異なり、かつ 0 と 2 のペア
            if (A[v] != 1 && A[u] != A[v]) {
                if (dp_parent[v] < INF) {
                    int opt_v_when_u_one = min(dp_one[v], dp_none[v]);
                    int cur_cost = sum_opt_one - opt_v_when_u_one + dp_parent[v];
                    cost_one = min(cost_one, cur_cost);
                }
            }
        }
    }

    dp_one[u] = cost_one;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    if (!(cin >> N)) return 0;

    vector<pair<int, int>> edges(N - 1);
    for (int i = 0; i < N - 1; ++i) {
        cin >> edges[i].first >> edges[i].second;
        edges[i].first--; edges[i].second--;
    }

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

    // 1. 同値な隣接頂点を Union-Find で縮約
    UnionFind uf(N);
    for (const auto& edge : edges) {
        int u = edge.first;
        int v = edge.second;
        if (A[u] == A[v]) {
            uf.unite(u, v);
        }
    }

    // 2. 縮約後の木 T' を構築
    adj.assign(N, vector<int>());
    for (const auto& edge : edges) {
        int u = uf.find(edge.first);
        int v = uf.find(edge.second);
        if (u != v) {
            adj[u].push_back(v);
            adj[v].push_back(u);
        }
    }

    // 多重辺の除去
    for (int i = 0; i < N; ++i) {
        if (uf.find(i) == i) {
            sort(adj[i].begin(), adj[i].end());
            adj[i].erase(unique(adj[i].begin(), adj[i].end()), adj[i].end());
        }
    }

    // 3. 木 DP の実行
    dp_parent.assign(N, INF);
    dp_one.assign(N, INF);
    dp_none.assign(N, INF);

    int root = uf.find(0);
    dfs(root, -1);

    // 根における最小残存頂点数を計算
    // 根が「値1の成分」に属する場合、その成分の根となるため +1 のコスト
    int min_remaining = min(dp_one[root] + 1, dp_none[root]);

    // 最大操作回数 = 初期頂点数 - 最小残存頂点数
    int ans = N - min_remaining;

    cout << ans << "\n";

    return 0;
}