트 리 dp hdu - 4616 - Game

제목 링크:
http://acm.hdu.edu.cn/showproblem.php?pid=4616
제목 의 대의:
나무 한 그루 에 게 각 노드 에 선물 값 과 trick 가 있 는 지, 한 노드 에 올 때마다 선물 을 받 아야 합 니 다. 만약 에 이 노드 에 trick 가 있 으 면 안 티 trick 기 회 를 낭비 합 니 다. 만약 에 처음에 C 번 의 안 티 trick 기회 가 있 으 면 가장 많은 선물 을 받 을 수 있 는 지 물 어보 면 기 회 는 다 쓴 후에 끝 납 니 다.방문 한 노드 는 다시 방문 할 수 없습니다.
문제 풀이 방향:
나무
나무 모양 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 시 에 만 뒤에서 업 데 이 트 됩 니 다.
PS2: 트 리 dp 를 많이 만들어 야 지.
코드:
 

#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;

}