http://acm.hdu.edu.cn/showproblem.php?pid=4616
转载自 http://blog.csdn.net/tri_integral/article/details/9499037
题意：
给出一棵树，树上每个节点都有权值，某些点有陷阱。可以任选起点，每个点只能走过一次，如果走到某点不能再走或者走到某个点恰好走了C个陷阱就停在该点，问最后路径上点权之和能得到的最大值。
题解：
树形DP。用dp[u][j]表示以u为根的子树上，从某点走到u且走过j个陷阱能得到的最大值;
考虑如果最优解走过了k个陷阱，如果k!=C，那么其起点和终点都可以为没有陷阱的点，如果k=C，那么起点或者终点至少有一点为有陷阱的点，所以dp数组还需要增加一维：dp[u][i][flag]，若flag=1，表示以u为根的子树上，从一个有陷阱的点走到u走过j个陷阱能得到的最大值，若flag=0，表示起点没有陷阱。
状态转移：
1) 当u点本身就有陷阱时，dp[u][j+1][flag]=max{dp[v][j][flag]+val[u]}，0<=j<C，v是u的儿子;
2) 当u点没有陷阱时，dp[u][j][flag]=max{dp[v][j][flag]+val[u]}，0<=j<C，特殊的，当j=C时，因为路上走过了C个陷阱，所以起点和终点不能同时为没有陷阱的点，所以只有flag=1，能用上式转移，也就是说dp[u][C][0]是不可能的情况。
这两种情况可以合成一种写。
更新ans：最优解可以看成两条链拼在一起，枚举两条链上陷阱的个数然后再拼起来。
注意答案为long long和dp数组的初始化。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 50050;
#define inf (1<<29)
int dp[maxn][4][2] , n , c , T;
int val[maxn] , trap[maxn] , ans;
struct Edge {
int v , next;
Edge () {}
Edge (int v , int next) : v(v) , next(next) {};
}edge[maxn << 1];
int E , head[maxn];
void init() {
E = 0; ans = 0; memset(head,-1,sizeof(head));
}
void addedge(int u,int v) {
edge[E] = Edge (v , head[u]); head[u] = E++;
edge[E] = Edge (u , head[v]); head[v] = E++;
}
void dfs(int u , int pa) {
dp[u][trap[u]][trap[u]] = val[u];
for(int i=head[u];i!=-1;i=edge[i].next) {
int v = edge[i].v;
if(v == pa) continue;
dfs(v , u);
for(int j=0;j<=c;j++)
for(int k=0;j+k<=c;k++) {
ans = max(ans , dp[u][j][1] + dp[v][k][1]);
if(j+k != c) ans = max(ans , dp[u][j][0] + dp[v][k][0]);
if(j != c) ans = max(ans , dp[u][j][0] + dp[v][k][1]);
if(k != c) ans = max(ans , dp[u][j][1] + dp[v][k][0]);
}
for(int j=0;j<c;j++) {
dp[u][j+trap[u]][1] = max(dp[u][j+trap[u]][1] , dp[v][j][1] + val[u]);
dp[u][j+trap[u]][0] = max(dp[u][j+trap[u]][0] , dp[v][j][0] + val[u]);
}
if(!trap[u]) dp[u][c][1] = max(dp[u][c][1] , dp[v][c][1] + val[u]);
}
}
int main() {
scanf("%d" , &T);
while(T--) {
scanf("%d%d" , &n, &c);
for(int i=0;i<n;i++) scanf("%d%d" , &val[i] , &trap[i]);
for(int i=0;i<n;i++) for(int j=0;j<=c;j++) for(int k=0;k<2;k++) dp[i][j][k] = - inf;
init();
for(int i=1;i<n;i++) {
int u , v ;
scanf("%d%d" , &u,&v);
addedge(u , v);
}
dfs(0, -1);
printf("%d
" , ans);
}
return 0;
}