Game
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)
Total Submission(s): 1734 Accepted Submission(s): 552
Problem Description
Nowadays, there are more and more challenge game on TV such as 'Girls, Rush Ahead'. Now, you participate int a game like this. There are N rooms. The connection of rooms is like a tree. In other words, you can go to any other room
by one and only one way. There is a gift prepared for you in Every room, and if you go the room, you can get this gift. However, there is also a trap in some rooms. After you get the gift, you may be trapped. After you go out a room, you can not go back to
it any more. You can choose to start at any room ,and when you have no room to go or have been trapped for C times, game overs. Now you would like to know what is the maximum total value of gifts you can get.
by one and only one way. There is a gift prepared for you in Every room, and if you go the room, you can get this gift. However, there is also a trap in some rooms. After you get the gift, you may be trapped. After you go out a room, you can not go back to
it any more. You can choose to start at any room ,and when you have no room to go or have been trapped for C times, game overs. Now you would like to know what is the maximum total value of gifts you can get.
Input
The first line contains an integer T, indicating the number of testcases.
For each testcase, the first line contains one integer N(2 <= N <= 50000), the number rooms, and another integer C(1 <= C <= 3), the number of chances to be trapped. Each of the next N lines contains two integers, which are the value of gift in the room and
whether have trap in this rooom. Rooms are numbered from 0 to N-1. Each of the next N-1 lines contains two integer A and B(0 <= A,B <= N-1), representing that room A and room B is connected.
All gifts' value are bigger than 0.
For each testcase, the first line contains one integer N(2 <= N <= 50000), the number rooms, and another integer C(1 <= C <= 3), the number of chances to be trapped. Each of the next N lines contains two integers, which are the value of gift in the room and
whether have trap in this rooom. Rooms are numbered from 0 to N-1. Each of the next N-1 lines contains two integer A and B(0 <= A,B <= N-1), representing that room A and room B is connected.
All gifts' value are bigger than 0.
Output
For each testcase, output the maximum total value of gifts you can get.
Sample Input
2 3 1 23 0 12 0 123 1 0 2 2 1 3 2 23 0 12 0 123 1 0 2 2 1
Sample Output
146 158
Source
Recommend
zhuyuanchen520
dp[i][j][flag]：在根为i的子树里，从一点跑到i的最大价值，flag为0代表起点不为陷阱，1代表起点为陷阱。
更新ans时，相当于将根为i的子树的一条树链合上i的相邻节点的一条树链，枚举得到最大值，更新ans即可。
每次更新全局最优之前，先在局部最优的情况下更新ans。
#include<map>
#include<string>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<queue>
#include<vector>
#include<iostream>
#include<algorithm>
#include<bitset>
#include<climits>
#include<list>
#include<iomanip>
using namespace std;
long long dp[50010][4][2],ans;
int c,w[50010],trap[50010];
vector<int>edge[50010];
void dfs(int pre,int from)
{
dp[from][trap[from]][trap[from]]=w[from];
for(int i=0;i<edge[from].size();i++)
{
int to=edge[from][i];
if(to==pre)
continue;
dfs(from,to);
for(int j=0;j<=c;j++)
for(int k=0;j+k<=c;k++)
{
if(j!=c&&k>0)
ans=max(ans,dp[from][j][0]+dp[to][k][1]);
if(k!=c&&j>0)
ans=max(ans,dp[from][j][1]+dp[to][k][0]);
if(j+k<c)
ans=max(ans,dp[from][j][0]+dp[to][k][0]);
if(j+k<=c)
ans=max(ans,dp[from][j][1]+dp[to][k][1]);
}
for(int j=0;j+trap[from]<=c;j++)
if(dp[from][j+trap[from]][0]<dp[to][j][0]+w[from])
dp[from][j+trap[from]][0]=dp[to][j][0]+w[from];
for(int j=1;j+trap[from]<=c;j++)
if(dp[from][j+trap[from]][1]<dp[to][j][1]+w[from])
dp[from][j+trap[from]][1]=dp[to][j][1]+w[from];
}
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int n;
scanf("%d%d",&n,&c);
for(int i=0;i<n;i++)
scanf("%d%d",w+i,trap+i);
for(int i=0;i<n;i++)
edge[i].clear();
while(--n)
{
int a,b;
scanf("%d%d",&a,&b);
edge[a].push_back(b);
edge[b].push_back(a);
}
ans=0;
memset(dp,0,sizeof(dp));
dfs(-1,0);
cout<<ans<<endl;
}
}