結果

問題 No.3514 Majority Driven Tree
コンテスト
ユーザー yt142857
提出日時 2026-03-25 13:58:49
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 5 ms / 2,000 ms
コード長 1,888 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,199 ms
コンパイル使用メモリ 348,204 KB
実行使用メモリ 6,400 KB
最終ジャッジ日時 2026-04-24 20:50:16
合計ジャッジ時間 4,124 ms
ジャッジサーバーID
（参考情報） 		judge3_1 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 37
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

//chatgpt(一時チャット)による出力
#include <bits/stdc++.h>
using namespace std;

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

    int N;
    cin >> N;
    vector<vector<int>> gph(N);
    for (int i = 0; i < N - 1; ++i) {
        int u, v;
        cin >> u >> v;
        --u; --v;
        gph[u].push_back(v);
        gph[v].push_back(u);
    }

    // 根を 0 に固定
    vector<int> parent(N, -1), order;
    order.reserve(N);
    stack<int> st;
    st.push(0);
    parent[0] = 0;

    while (!st.empty()) {
        int v = st.top();
        st.pop();
        order.push_back(v);
        for (int to : gph[v]) {
            if (to == parent[v]) continue;
            parent[to] = v;
            st.push(to);
        }
    }

    vector<long long> f(N, 0), gg(N, 0);
    const long long INF = (1LL << 60);

    for (int idx = N - 1; idx >= 0; --idx) {
        int v = order[idx];

        vector<long long> diffs;
        long long base = 0;

        for (int to : gph[v]) {
            if (to == parent[v]) continue;
            base += gg[to];
            diffs.push_back(f[to] - gg[to]);
        }

        sort(diffs.begin(), diffs.end());

        long long pref = 0;
        vector<long long> ps(diffs.size() + 1, 0);
        for (int i = 0; i < (int)diffs.size(); ++i) {
            ps[i + 1] = ps[i] + diffs[i];
        }

        int deg = (int)gph[v].size();
        int need0 = deg / 2 + 1;   // 親が白
        int need1 = need0 - 1;     // 親が黒

        auto take = [&](int need) -> long long {
            if (need < 0) need = 0;
            if (need > (int)diffs.size()) return INF;
            return base + ps[need];
        };

        long long seed_v = 1 + base;      // v を最初に塗る
        f[v] = min(seed_v, take(need0));
        gg[v] = min(seed_v, take(need1));
    }

    cout << f[0] << '\n';
    return 0;
}
0