CPSCO 2019 session2 E - Mogu Mogu Gummi (600 点)

二乗の木 DP のいい練習問題！！！！！
ついでに DP で最適化したい対象を入れ替えるタイプの問題でもある。そのようなタイプとして難しい問題としては、以下がある。

drken1215.hatenablog.com

問題へのリンク

問題概要

頂点の重みつきの根つき木が与えられる。根はノード 0 である。以下の操作を好きなだけ行うことができる。

• 根以外の頂点 v を一つ選ぶ。ただし、根と v とが連結でなければならない。
• 根と v とを結ぶパス上の辺の重みを一律に 1 下げる。ただし重みが 0 になった辺についてはその場で取り除く

好きなだけ操作を行った後に、最大で何個の連結成分にわけることができるか。

制約

• 

考えたこと

• dp[ v ][ k ] := v を根とする根つき木において、k 本の辺を除去する状況にするために必要な重み下げコストの最小値

とする。dp[ 0 ][ k ] が INF 以下になる最大の k に対して k + 1 が答え。これは木 DP で求められるのだが、一見すると かかるように見えるが、実は二乗の木 DP というやつ。

頂点 v の更新自体に DP が必要になる。サブ DP として

• sdp[ i ][ k ] := v の子供 i 個分を見た段階で、k 辺を除去するのに必要な最小コスト

とすると

v 直下の i 番目の辺 (接続先ノード ch とする) を切らない場合

dp[ ch ][ k ] < w となっている場合に限り、

chmin(sdp[ i + 1 ][ j + k ], sdp[ i ][ j ] + dp[ ch ][ k ]);

v 直下の i 番目の辺を切る場合 (その下の k 個の辺除去も維持)

dp[ ch ][ k ] <= w となっている場合に限り、

chmin(sdp[ i + 1 ][ j + k + 1 ] , sdp[ i ][ j ] + w);

v 直下の i 番目の辺を切り、その下の辺は切らない場合

chmin(sdp[ i + 1 ][ j + 1 ], sdp[ i ][ j ] + w);

実装上は、上記の sdp に関する DP は in-place に行うこととし、添字 i の部分は省略した。

#include <iostream>
#include <vector>
using namespace std;
const long long INF = 1LL<<60;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

using Edge = pair<int, long long>;
using Graph = vector<vector<Edge>>;

int N;
Graph G;

vector<int> subtree_size;
vector<vector<long long>> dp;

void rec(int v) {
    subtree_size[v] = 1;
    for (int i = 0; i < G[v].size(); ++i) {
        int to = G[v][i].first;
        rec(to);
        subtree_size[v] += subtree_size[to];
    }
    dp[v].assign(subtree_size[v]+1, INF);

    int s = 1;
    vector<long long> sdp(subtree_size[v]+1, INF);
    sdp[0] = 0;
    for (int i = 0; i < G[v].size(); ++i) {
        int to = G[v][i].first;
        long long w = G[v][i].second;
        for (int j = s; j >= 0; --j) {
            for (int k = 0; k < subtree_size[to]; ++k) {
                // w より多くの力は掛からない
                if (dp[to][k] > w) continue;
                
                if (dp[to][k] == w) {
                    chmin(sdp[j+k+1], sdp[j] + dp[to][k]);
                }
                else {
                    chmin(sdp[j+k], sdp[j] + dp[to][k]);
                    chmin(sdp[j+k+1], sdp[j] + w);
                }
            }
        }
        s += subtree_size[to];
    }           
    for (int j = 0; j <= subtree_size[v]; ++j) dp[v][j] = sdp[j];
}

long long solve() {
    subtree_size.assign(N, 0);
    dp.assign(N, vector<long long>());
    rec(0);
    int res = 0;
    for (int i = 0; i <= N; ++i) {
        if (dp[0][i] == INF) break;
        res = i + 1;
    }
    return res;
}

int main() {
    cin >> N;
    G.assign(N, vector<Edge>());
    for (int i = 0; i < N-1; ++i) {
        int p; cin >> p;
        long long H; cin >> H;
        G[p].push_back({i+1, H});
    }
    cout << solve() << endl;
}