题目链接：http://poj.org/problem?id=1155
题目大意：电视台要广播电视节目，要经过中转机构，到观众。从电视台到中转商到观众是一个树形结构，经过一条边需要支付成本。现在给你每两个节点之间传播的成本，给你每个观众会付的钱，问你电视台在不亏本的情况下最多能给多少个观众看节目。
这是我的第一道树形dp。。无耻的看了题解。。
设计状态：dp[u][i]代表以u为根的子树中有i个观众，能够得到的最大收入。
状态转移：dp[u][i] = max(dp[u][i],dp[u][i-j]+dp[v][j]-cost[u][v]);
用java写了一个版本。。总是RE，就不知道是为什么了。。
代码：
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std; const int MAX_N = ;
const int INF = ;
struct EDGE{
int to,cost;
int next;
};
EDGE edge[MAX_N<<];
int ptr,head[MAX_N];
int cost[MAX_N]; void init(){
memset(edge,-,sizeof(edge));
memset(head,-,sizeof(head));
ptr = ;
} void add_edge(int from,int to,int cost){
edge[ptr].to = to;
edge[ptr].cost = cost;
edge[ptr].next = head[from];
head[from] = ptr++;
} int N,M;
int dp[MAX_N][MAX_N];
bool vis[MAX_N];
int sum[MAX_N]; void DP(int u){
if( vis[u] ) return;
vis[u] = true; dp[u][] = ;
int tot = ; for(int i=head[u];~i;i=edge[i].next){
int v = edge[i].to;
if( !vis[v] ){
tot++;
DP( v );
sum[u] += sum[v];
}
} if( tot== ){
sum[u] = ;
dp[u][] = cost[u];
} else {
for(int k=head[u];~k;k=edge[k].next){
int v = edge[k].to;
for(int j=sum[u];j>=;--j){
for(int i=;i<=sum[v];i++){
if( j>=i && dp[u][j-i]!=-INF && dp[v][i]!=-INF){
dp[u][j] = max(dp[u][j],dp[u][j-i]+dp[v][i]-edge[k].cost);
}
}
}
}
}
} int main(){
while(scanf("%d%d",&N,&M)!=EOF){
init();
int k;
for(int i=;i<=N-M;i++){
scanf("%d",&k);
for(int j=;j<k;j++){
int a,c;
scanf("%d%d",&a,&c);
add_edge(i,a,c);
add_edge(a,i,c);
}
} for(int i=N-M+;i<=N;i++){
scanf("%d",&cost[i]);
} memset(vis,,sizeof(vis));
memset(sum,,sizeof(sum));
for(int i=;i<=N;i++){
for(int j=;j<=N;j++){
dp[i][j] = -INF;
}
}
DP();
for(int i=N;i>=;--i){
if( dp[][i] >= ) {
printf("%d\n",i);
break;
}
} }
return ;
}