http://acm.hdu.edu.cn/showproblem.php?pid=4616
题意：
给出一棵树，每个顶点有权值，还有存在陷阱，现在从任意一个顶点出发，并且每个顶点只能经过一次，如果经过了c个陷阱就不能再走了，计算最大能获得的权值和。
思路：
有点像树链剖分，对于一个以u为根的子树，因为每个顶点只能经过一次，那我们只能选择它的一个子树往下走。就像是把这棵树分成许多链，最后再连接起来。
这道题目麻烦的地方是陷阱的处理，用d【u】【j】【0/1】表示以u为根的某一子节点经过j个陷阱后到达u的最大权值和，0/1表示起点是否有陷阱。
假设当前到达u时经过了k个陷阱，分下面几种情况进行讨论：
①如果k==c，那么起点和终点至少有一个是陷阱（可能有些人会认为终点一定会是陷阱，这样是没错的，因为起点和终点时相对的，你也可以把起点看做终点）。
②如果k<c，那么起点和终点是否是陷阱是任意的，可以有也可以没有。
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<sstream>
#include<vector>
#include<stack>
#include<queue>
#include<cmath>
#include<map>
#include<set>
using namespace std;
typedef long long ll;
typedef pair<int,int> pll;
const int INF = 0x3f3f3f3f;
const int maxn = + ; int n,c;
int ans;
int val[maxn], trap[maxn];
int d[maxn][][];
vector<int> G[maxn]; void dfs(int u, int fa)
{
d[u][trap[u]][trap[u]]=val[u]; for(int i=;i<G[u].size();i++)
{
int v=G[u][i];
if(v==fa) continue;
dfs(v,u); //计算以u为根的子树所能获得的最大值，也就是将子树的链进行连接
for(int j=;j<=c;j++)
{
for(int k=;j+k<=c;k++)
{
if(j!=c) ans=max(ans,d[u][j][]+d[v][k][]);
if(k!=c) ans=max(ans,d[u][j][]+d[v][k][]);
if(j+k<c) ans=max(ans,d[u][j][]+d[v][k][]); //起点和终点都可以为非陷阱
if(k+j<=c) ans=max(ans,d[u][j][]+d[v][k][]); //起点和终点都可以为陷阱
}
} for(int j=;j+trap[u]<=c;j++) //更新以u的根的子树中权值最大的链
{
d[u][j+trap[u]][]=max(d[u][j+trap[u]][],d[v][j][]+val[u]);
//这儿要注意一下，如果j=0时，要么就不能从有陷阱的起点出发
if(j!=) d[u][j+trap[u]][]=max(d[u][j+trap[u]][],d[v][j][]+val[u]);
}
}
} int main()
{
//freopen("in.txt","r",stdin);
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&c);
for(int i=;i<n;i++) G[i].clear(); for(int i=;i<n;i++)
scanf("%d%d",&val[i],&trap[i]); for(int i=;i<n;i++)
{
int u,v;
scanf("%d%d",&u,&v);
G[u].push_back(v);
G[v].push_back(u);
} ans=;
memset(d,,sizeof(d));
dfs(,-);
printf("%d\n",ans);
}
return ;
}