結果

問題 No.3283 Labyrinth and Friends
コンテスト
ユーザー srjywrdnprkt
提出日時 2025-10-15 18:05:13
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 8 ms / 2,000 ms
コード長 1,729 bytes
コンパイル時間 3,105 ms
コンパイル使用メモリ 283,892 KB
実行使用メモリ 7,720 KB
最終ジャッジ日時 2025-10-15 18:05:18
合計ジャッジ時間 5,541 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 45
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
//#include <atcoder/modint>

using namespace std;
//using namespace atcoder;
using ll = long long;
//using mint = modint998244353;

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

    /*
       dp(i, j) = 頂点iの部分木でステータスをjにするのに必要なコストの最小値

       最初に
       dp(i, s_i) = c_i
       とし、dp(j, t)をマージするとき、
       コストdp(j, t)、価値tの商品を選ぶナップサック問題。
       このままだと間に合わないが2乗の木DPに落とし込める。
    */

    ll N, X;
    cin >> N >> X;
    vector<vector<ll>> E(N);
    for (int i=1; i<N; i++){
        ll p;
        cin >> p;
        p--;
        E[p].push_back(i);
    }
    vector<ll> s(N), c(N);
    
    for (int i=1; i<N; i++) cin >> c[i] >> s[i];

    vector<ll> sz(N); //頂点iの部分木のsの和
    auto dfs=[&](auto self, ll from)->vector<ll>{
        sz[from] = s[from];
        ll ss = sz[from];
        vector<ll> dp(ss+1, 1e18);
        dp[ss] = c[from];
        for (auto to : E[from]){
            auto pd = self(self, to);
            ll _ss=sz[to], nss=ss+_ss;
            vector<ll> merged(nss+1, 1e18);
            for (int i=0; i<=ss; i++){
                for (int j=0; j<=_ss; j++){
                    merged[i+j] = min(merged[i+j], dp[i] + pd[j]);
                    merged[i] = min(merged[i], dp[i]);
                }
            }
            swap(dp, merged);
            sz[from] = nss;
            ss = nss;
        }
        return dp;
    };

    auto dp = dfs(dfs, 0);
    ll ans=1e18;
    for (int i=X; i<dp.size(); i++) ans = min(ans, dp[i]);
    cout << ans << endl;

    return 0;
}
0