結果

問題 No.3769 Even Contraction
コンテスト
ユーザー marc2825
提出日時 2026-10-04 20:42:50
言語 C++17
(gcc 15.3.0 + boost 1.92.0 + ACL)
コンパイル:
g++-15 -O2 -lm -std=c++17 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
RE  
実行時間 -
コード長 2,433 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,857 ms
コンパイル使用メモリ 234,772 KB
実行使用メモリ 9,928 KB
最終ジャッジ日時 2026-10-16 20:56:31
合計ジャッジ時間 9,164 ms
ジャッジサーバーID
（参考情報） 		judge4_0 / judge3_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 17 RE * 30
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

// 愚直全探索
#include <bits/stdc++.h>
using namespace std;

using ull = unsigned long long;

struct Node {
    ull mask; // この縮約頂点に含まれる元頂点集合
    int val;  // 0,1,2

    bool operator<(const Node& rhs) const {
        if (mask != rhs.mask) return mask < rhs.mask;
        return val < rhs.val;
    }
};

int N;
vector<pair<int,int>> E;

// memo[state] = ここから可能な最大操作回数
map<vector<Node>, int> memo;


// state 内で、元頂点 v がどの縮約頂点に属するか
vector<int> get_id(const vector<Node>& state) {
    vector<int> id(N);

    for (int i = 0; i < (int)state.size(); i++) {
        ull m = state[i].mask;

        for (int v = 0; v < N; v++) {
            if ((m >> v) & 1ULL) {
                id[v] = i;
            }
        }
    }

    return id;
}


int dfs(vector<Node> state) {
    // mask 順に canonicalize
    sort(state.begin(), state.end());

    if (memo.count(state)) {
        return memo[state];
    }

    int M = state.size();

    auto id = get_id(state);

    // 現在の縮約木の辺
    set<pair<int,int>> edges;

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

        if (a == b) continue;

        if (a > b) swap(a,b);

        edges.insert({a,b});
    }

    int ans = 0;

    for (auto [a,b] : edges) {
        int x = state[a].val;
        int y = state[b].val;

        // 偶奇が異なるので縮約不可
        if ((x & 1) != (y & 1)) {
            continue;
        }

        vector<Node> nxt;

        for (int i = 0; i < M; i++) {
            if (i == a || i == b) continue;

            nxt.push_back(state[i]);
        }

        Node merged;
        merged.mask = state[a].mask | state[b].mask;
        merged.val = (x + y) / 2;

        nxt.push_back(merged);

        ans = max(
            ans,
            1 + dfs(nxt)
        );
    }

    return memo[state] = ans;
}


void solve() {
    cin >> N;

    E.resize(N-1);

    for (auto &[u,v] : E) {
        cin >> u >> v;
        --u;
        --v;
    }

    vector<int> A(N);

    for (int &x : A) {
        cin >> x;
    }

    assert(N <= 63);

    vector<Node> init;

    for (int v = 0; v < N; v++) {
        init.push_back({
            1ULL << v,
            A[v]
        });
    }

    memo.clear();

    cout << dfs(init) << '\n';
}


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

    solve();
}
0