yukicoder No.417 チューリップバブル

O(NM^2) だと結構厳しめの制約だと思ってだいぶ悩んでいた。

問題

No.417 チューリップバブル - yukicoder

解法

O(NM^2) の木 dp をします。

まず考察ですが, 最後に頂点 0 に戻ってこなければならないことから, v -> u と辺を降りた場合, 再び u -> v と戻ってこなければなりません。つまり, 通る辺はすべて 2 回通ることになります。

dp[v][rest] = (頂点 v の時点で残り時間が rest の時の最大利益) とすると, v の子が ch として,

dp[v][rest] = max(dp[ch][j-(v から ch に行くコスト)] + dp[v][rest-j]) + U[v]

というように更新していけば良いです。

const int MAXN = 222;
const int MAXM = 1010;
int N, M;
ll U[MAXN];

struct Edge {
    int to;
    int cost;
    Edge() {}
    Edge(int t, int c) : to(t), cost(c) {}
};

vector<Edge> G[MAXN];
ll dp[MAXN][MAXM];

void dfs(int v, int p) {
    for (Edge e : G[v]) if (e.to != p) {
        dfs(e.to, v);
    }
    for (Edge e : G[v]) if (e.to != p) {
        for (int i = M; i >= 0; i--) {
            for (int j = e.cost; j <= i; j++) {
                dp[v][i] = max(dp[v][i], dp[v][i-j] + dp[e.to][j-e.cost]);
            }
        }
    }
    for (int i = 0; i <= M; i++)
        dp[v][i] += U[v];
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> N >> M;
    M /= 2;
    for (int i = 0; i < N; i++)
        cin >> U[i];
    for (int i = 0; i < N-1; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        G[a].emplace_back(b, c);
        G[b].emplace_back(a, c);
    }
    dfs(0, -1);
    ll ans = 0;
    for (int i = 0; i <= M; i++)
        ans = max(ans, dp[0][i]);
    cout << ans << endl;
    return 0;
}