题意：电视台发送信号给很多用户，每个用户有愿意出的钱，电视台经过的路线都有一定费用，求电视台不损失的情况下最多给多少用户发送信号。

转自：http://www.cnblogs.com/andre0506/archive/2012/10/09/2717441.html

思路：

基础树形DP。

x表示当前在的节点。j表示选j个收听电视。

f[x][j]=max(f[x][j],f[x.son][k]+f[x][j-k]-w[i]);

// by SiriusRen

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

int n,m,jy,v[3005],w[3005],next[3005],first[3005],size[3005],tot=0;

int f[3005][3005];

void dfs(int x){

    for(int i=first[x];~i;i=next[i]){

        dfs(v[i]);

        size[x]+=size[v[i]];

        for(int j=size[x];j>=0;j--)

            for(int k=0;k<=size[v[i]];k++)

                f[x][j]=max(f[x][j],f[v[i]][k]+f[x][j-k]-w[i]);

    }

}

int main(){

    memset(first,-1,sizeof(first));

    memset(f,0xcf,sizeof(f));

    scanf("%d%d",&n,&m);

    for(int i=1;i<=n;i++)f[i][0]=0;

    for(int i=1;i<=n-m;i++){

        scanf("%d",&jy);

        while(jy--){

            scanf("%d%d",&v[tot],&w[tot]);

            next[tot]=first[i];

            first[i]=tot++;

        }

    }

    for(int i=1;i<=m;i++)scanf("%d",&f[i+n-m][1]),size[i+n-m]=1;

    dfs(1);

    for(int i=n;i>=0;i--)

        if(f[1][i]>=0){printf("%d\n",i);break;}

}