题目链接：
http://acm.hdu.edu.cn/showproblem.php?pid=4616
题目大意：
给一棵树，每个节点有一个礼物值及是否有trick，每来到一个节点必须拿礼物，如果该节点有trick则浪费一个抗trick机会，如果一开始有C次抗trick的机会，问最多可以拿多少值的礼物，机会用完后就结束了。访问了的节点不能再次访问。
解题思路：
树形dp啊。
树形dp很不熟悉阿阿阿阿阿阿阿阿。。。。
dp[i][j][0]表示从节点i开始，有j次机会，在子树中最大的能拿到礼物的值。
dp[i][j][1]表示从节点i开始，有j次机会，在子树中次大的能拿到礼物的值。
by[i][j]表示i节点，有j次机会时，得到最大值的那个直接儿子标号。
先以任意一点为根，dfs一遍。求出从每个节点的开始的在子树中的最大值和次大值。
再以同一点为根，dfs一遍，参数维护一个以父亲为开始节点且不经过该节点的最大值。求出该节点出发的在整棵树中的最大值。
PS:
注意此题麻烦的地方是，当机会恰好用完时，游戏结束，不能累加后面的0机会值。
所以要分该节点是否有trick来判断，如果有trick的话，只有j>=2时有从后面更新。
ＰＳ２：要多做树形ｄｐ啊。
代码：
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#define eps 1e-6
#define INF 0x1f1f1f1f
#define PI acos(-1.0)
#define ll __int64
#define lson l,m,(rt<<1)
#define rson m+1,r,(rt<<1)|1
//#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;
//freopen("data.in","r",stdin);
//freopen("data.out","w",stdout);
#define Maxn 55000
ll dp[Maxn][5][2]; //dp[i][j][0]表示从i节点开始有j个机会，在子树中能达到的最大值
int tra[Maxn],val[Maxn],cnt,n,c;
int by[Maxn][5];
ll ans;
struct Edge //邻接表
{
int v;
struct Edge * next;
}edge[Maxn<<1],*head[Maxn<<1];
void add(int a,int b)
{
++cnt;
edge[cnt].v=b,edge[cnt].next=head[a];
head[a]=&edge[cnt];
}
ll Max(ll a,ll b)
{
return a>b?a:b;
}
void dfs1(int pre,int cur)
{
struct Edge * p=head[cur];
bool flag=true;
while(p)
{
if(p->v!=pre)
{
flag=false;
dfs1(cur,p->v); //先计算出子树情况
if(tra[cur]) //该节点有trick
{
dp[cur][1][0]=val[cur];
for(int i=2;i<=c;i++) //必须大于等于2的情况才可能从后面更新
{
if(dp[p->v][i-1][0]+val[cur]>=dp[cur][i][0])
{
dp[cur][i][1]=dp[cur][i][0];//更新次大
dp[cur][i][0]=dp[p->v][i-1][0]+val[cur];
by[cur][i]=p->v;
}
else if(dp[p->v][i-1][0]+val[cur]>dp[cur][i][1])
{ //更新次大
dp[cur][i][1]=dp[p->v][i-1][0]+val[cur];
}
}
}
else
{ //如果没有trick，则可以到达其他点任何点
for(int i=0;i<=c;i++)
{
if(dp[p->v][i][0]+val[cur]>=dp[cur][i][0])
{
dp[cur][i][1]=dp[cur][i][0];
dp[cur][i][0]=dp[p->v][i][0]+val[cur];
by[cur][i]=p->v;
}
else if(dp[p->v][i][0]+val[cur]>dp[cur][i][1])
{
dp[cur][i][1]=dp[p->v][i][0]+val[cur];
}
}
}
}
p=p->next;
}
if(flag) //叶子节点单独处理
{
for(int i=tra[cur];i<=c;i++)
dp[cur][i][0]=val[cur];
}
}
void dfs2(int pre,int cur,ll *aa)
{
ll MM=0;
if(tra[cur])
{
MM=dp[cur][c][0];//从子树中找
if(c>=2)
MM=Max(MM,aa[c-1]+val[cur]); //从父亲找
}
else
MM=Max(dp[cur][c][0],aa[c]+val[cur]);
if(MM>ans)
ans=MM;
/* printf("cur:%d ans:%I64d
",cur,MM);
for(int i=0;i<=c;i++)
printf("aa[%d]:%I64d ",i,aa[i]);
putchar('
');
system("pause");*/
struct Edge * p=head[cur];
while(p)
{
if(p->v!=pre)
{
ll tt[5]={0}; //tt[i]表示父亲有i次机会且不通过该儿子时能达到的最大值
if(tra[cur])
{
tt[1]=dp[cur][1][0]; //注意更新
for(int i=2;i<=c;i++)
{
if(p->v!=by[cur][i]) //最大值是该儿子，用次大的来更新
tt[i]=Max(aa[i-1]+val[cur],dp[cur][i][0]);
else
tt[i]=Max(aa[i-1]+val[cur],dp[cur][i][1]);
}
}
else
{
for(int i=0;i<=c;i++)
{
if(p->v!=by[cur][i])
tt[i]=max(aa[i]+val[cur],dp[cur][i][0]);
else
tt[i]=max(aa[i]+val[cur],dp[cur][i][1]);
}
}
/* for(int i=0;i<=c;i++)
printf("i:%d %d
",i,tt[i]);*/
dfs2(cur,p->v,tt);
}
p=p->next;
}
}
int main()
{
int t,a,b;
//freopen("1006.in","r",stdin);
//freopen("1006ans.out","w",stdout);
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&c);
memset(by,-1,sizeof(by));
memset(head,NULL,sizeof(head));
for(int i=0;i<n;i++)
scanf("%d%d",&val[i],&tra[i]);
cnt=0;
for(int i=1;i<n;i++)
{
scanf("%d%d",&a,&b);
add(a,b);
add(b,a);
}
memset(dp,0,sizeof(dp));
ans=0;
dfs1(-1,0);
ll tt[5]={0};
dfs2(-1,0,tt);
printf("%I64d
",ans);
}
return 0;
}