POJ 1155 TELE

http://poj.org/problem?id=1155

木構造をしたTV-Networkが与えられます。根が放送局、葉が視聴者、それ以外が中継所です。通信にはコストcがかかります。また、視聴者は放送を受信できた場合p円を払います。赤字にならないように放送をするとき、放送を受信できる視聴者数の最大を求めよ、という問題。
　コメントに解き方をメモしておいたのでそのままコードを貼ります。

//POJ 1155 TELE
//苦戦しましたが面白い問題でした。
// dp[i][j] = ノードiからj人に配信するときのコスト　とし、各頂点Vにおいてdfs(子)を呼び出し、dp[Vc](VcはVの子)を確定させます。
// これをもとにdp[V]を更新します。式は
// dp[V][j] = min(dp[V][j - k] + dp[Vc][k] + V-Vc_cost)(VcはVの子、0<=j, k<=(Vから到達可能な葉の数))
//という感じです。jを後ろから回さないと、Vcから複数通り選べることになってしまいうまくいきません。これはナップザック問題の個数制限あり/なしと似ている気がしますが、実力不足のため理解に時間がかかりました。
//普通にメモ化再帰を書こうとしたら全くダメでした。最初から式を考えたほうが見通しが良かったと思います。
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
const int INF = 1000000000;
#define REP(i,s,n) for(int i=(int)(s);i<(int)(n);i++)
#define rep(i,n) REP(i, 0, n)
struct Edge{
    int to, cost;
    Edge(int to) : to(to) {}
    Edge(int to, int cost) : to(to), cost(cost) {}
};

vector<Edge> edges[3000];//0-indexed
int pay[3000];
int N, M;
int dp[3000][3001];//ノードiからj人に配信するときのコスト
int to_leaf[3000];//ノードiから到達可能な葉の数を記録

void init(){
    memset(to_leaf, 0, sizeof(to_leaf));
    rep(i, 3000)
      rep(j, 3001)
        dp[i][j] = !j ? 0 : INF;
}

void dfs(int V){//頂点Vに来たらVより下の頂点へ再帰→dp[V][i(0 ~ M)]を確定
    if(N - M <= V){
        dp[V][1] = pay[V] * -1;
        to_leaf[V] = 1;
        return;
    }
    rep(i, edges[V].size()){
        int Vc = edges[V][i].to, cost = edges[V][i].cost;
        dfs(Vc);
        to_leaf[V] += to_leaf[Vc];
        for(int j = to_leaf[V]; j >= 0; --j)
          for(int k = j; k <= j; k++)
            dp[V][j] = min(dp[V][j], dp[V][j - k] + dp[Vc][k] + cost);
    }
    return;
}

int main(){
    scanf("%d%d", &N, &M);
    int a, c;
    rep(i, N - M){
        int k; scanf("%d", &k);
        rep(j, k){
            scanf("%d%d", &a, &c);
            a--;
            edges[i].push_back(Edge(a, c));
        }
    }
    REP(i, N - M, N) scanf("%d", pay + i);
    init();
    dfs(0);
    int ans = -1;
    rep(i, M + 1)
      if(dp[0][i] <= 0)
        ans = max(ans, i);
    printf("%d\n", ans);
    return 0;
}

　ところで、この問題の動的計画法のかたち、以下の問題に似ている気がします。
http://mio-hirona.hatenablog.com/entry/2016/04/29/222020
種類制約つきのナップザック問題で、使う種類ごとにDPをまわしていくと解ける、という問題です。使う頂点（子）ごとにナップザック的なことをしてテーブルを更新していくという点で今回の問題も考え方としては近い気がします。だからどうだということもないのですが、たくさんループを回す動的計画法の問題は難しいです。