題意：有棵樹上有n個結點，每個點有若干價值的禮物，有些點可能有餡阱，有m次掉入餡阱的機會，但
第m次掉入餡阱後則不能再走，並每個點最多只能經過一次。問：可以任意點為起點，最多可以拿
到總價值多大的禮物。
分析：
分兩種情況：
Ⅰ、以餡點做為起始點
Ⅱ、以非餡阱點做為起始點
代碼：
一、從下往上搜（自己寫的代碼）
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
typedef long long LL;
const int maxn=55555;
vector<int>Tree[maxn];
LL val[maxn],dp[2][maxn][5],ans;
int vid[maxn],par[maxn];
int n,m;
LL max(LL a,LL b){
return a>b?a:b;
}
void DFS(int cnt){
int len=Tree[cnt].size(),q=0;
for(int i=0;i<len;++i){
int son=Tree[cnt][i];
if(par[son]==son&&son){
par[son]=cnt; q=1;
DFS(son);
if(!vid[cnt]&&!vid[son])
dp[0][cnt][0]=max(dp[0][cnt][0],dp[0][son][0]+val[cnt]);
for(int i=1; i<=m; ++i){
if(vid[son])
dp[0][cnt][i]=max(dp[0][cnt][i], dp[0][son][i-1]+val[cnt]);
else
dp[0][cnt][i]=max(dp[0][cnt][i], dp[0][son][i]+val[cnt]);
}
if(vid[cnt]){
for(int i=1;i<=m;++i)
dp[1][cnt][i]=max(dp[1][cnt][i],dp[1][son][i-1]+val[cnt]);
}else {
for(int i=1;i<=m;++i){
if(dp[1][son][i])
dp[1][cnt][i]=max(dp[1][cnt][i],dp[1][son][i]+val[cnt]);
}
}
}
}
ans=max(ans,max(dp[0][cnt][m],dp[1][cnt][m]));
}
void comp1(int cnt,int a,int b){ // vid[cnt]=1
if(vid[a]){
for(int i=1;i<m;++i){
LL k=dp[1][b][m-i-1];
if(m-i-1) k=max(k,dp[0][b][m-i-2]);
ans=max(ans,dp[0][a][i]+val[cnt]+k);
}
}
else {
for(int i=1;i<=m;++i){
LL k=dp[1][b][m-i];
if(m-i) k=max(k,dp[0][b][m-i-1]);
ans=max(ans,dp[0][a][i]+val[cnt]+k);
}
}
}
void comp2(int cnt,int a,int b){ // vid[cnt]=0
if(vid[a]){
for(int i=1;i<=m;++i){
LL k=dp[1][b][m-i];
if(m-i) k=max(k,dp[0][b][m-i-1]);
ans=max(ans,dp[0][a][i]+val[cnt]+k);
}
}
else {
for(int i=1;i<=m;++i){
LL k=dp[1][b][m-i+1];
if(m-i+1) k=max(k,dp[0][b][m-i]);
ans=max(ans,dp[0][a][i]+val[cnt]+k);
}
}
}
void DFS_DP(int cnt){
int len=Tree[cnt].size();
for(int i=0;i<len;++i){
int a=Tree[cnt][i];
if(par[a]!=cnt) continue;
for(int j=i+1;j<len;++j){
int b=Tree[cnt][j];
if(par[b]!=cnt)continue;
if(vid[cnt]) {
comp1(cnt,a,b);
comp1(cnt,b,a);
} else {
comp2(cnt,a,b); comp2(cnt,b,a);
}
}
}
for(int i=0;i<len;++i){
int son=Tree[cnt][i];
if(par[son]!=cnt) continue;
DFS_DP(son);
}
}
void print();
int main(){
int T; scanf("%d",&T);
while(T--){
memset(dp,0,sizeof(dp));
scanf("%d%d",&n,&m);
for(int i=0;i<n;++i){
Tree[i].clear();
scanf("%I64d%d",val+i,vid+i);
par[i]=i;
if(vid[i])
for(int j=1; j<=m; ++j)
dp[0][i][j]=dp[1][i][j]=val[i];
else
for(int j=0; j<=m; ++j)
dp[0][i][j]=val[i];
}
for(int i=1;i<n;++i){
int a,b; scanf("%d%d",&a,&b);
Tree[a].push_back(b);
Tree[b].push_back(a);
}
ans=0LL;
DFS(0);
DFS_DP(0);
printf("%I64d\n",ans);
}
return 0;
}
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
typedef long long LL;
const int maxn=55555;
vector<int>Tree[maxn];
LL val[maxn],dp[2][maxn][5],ans;
int vid[maxn],par[maxn];
int n,m;
LL max(LL a,LL b){
return a>b?a:b;
}
void DFS(int cnt){
int len=Tree[cnt].size(),q=0;
for(int i=0;i<len;++i){
int son=Tree[cnt][i];
if(par[son]==son&&son){
par[son]=cnt; q=1;
DFS(son);
if(!vid[cnt]&&!vid[son])
dp[0][cnt][0]=max(dp[0][cnt][0],dp[0][son][0]+val[cnt]);
for(int i=1; i<=m; ++i){
if(vid[son])
dp[0][cnt][i]=max(dp[0][cnt][i], dp[0][son][i-1]+val[cnt]);
else
dp[0][cnt][i]=max(dp[0][cnt][i], dp[0][son][i]+val[cnt]);
}
if(vid[cnt]){
for(int i=1;i<=m;++i)
dp[1][cnt][i]=max(dp[1][cnt][i],dp[1][son][i-1]+val[cnt]);
}else {
for(int i=1;i<=m;++i){
if(dp[1][son][i])
dp[1][cnt][i]=max(dp[1][cnt][i],dp[1][son][i]+val[cnt]);
}
}
}
}
ans=max(ans,max(dp[0][cnt][m],dp[1][cnt][m]));
}
void comp1(int cnt,int a,int b){ // vid[cnt]=1
if(vid[a]){
for(int i=1;i<m;++i){
LL k=dp[1][b][m-i-1];
if(m-i-1) k=max(k,dp[0][b][m-i-2]);
ans=max(ans,dp[0][a][i]+val[cnt]+k);
}
}
else {
for(int i=1;i<=m;++i){
LL k=dp[1][b][m-i];
if(m-i) k=max(k,dp[0][b][m-i-1]);
ans=max(ans,dp[0][a][i]+val[cnt]+k);
}
}
}
void comp2(int cnt,int a,int b){ // vid[cnt]=0
if(vid[a]){
for(int i=1;i<=m;++i){
LL k=dp[1][b][m-i];
if(m-i) k=max(k,dp[0][b][m-i-1]);
ans=max(ans,dp[0][a][i]+val[cnt]+k);
}
}
else {
for(int i=1;i<=m;++i){
LL k=dp[1][b][m-i+1];
if(m-i+1) k=max(k,dp[0][b][m-i]);
ans=max(ans,dp[0][a][i]+val[cnt]+k);
}
}
}
void DFS_DP(int cnt){
int len=Tree[cnt].size();
for(int i=0;i<len;++i){
int a=Tree[cnt][i];
if(par[a]!=cnt) continue;
for(int j=i+1;j<len;++j){
int b=Tree[cnt][j];
if(par[b]!=cnt)continue;
if(vid[cnt]) {
comp1(cnt,a,b);
comp1(cnt,b,a);
} else {
comp2(cnt,a,b); comp2(cnt,b,a);
}
}
}
for(int i=0;i<len;++i){
int son=Tree[cnt][i];
if(par[son]!=cnt) continue;
DFS_DP(son);
}
}
void print();
int main(){
int T; scanf("%d",&T);
while(T--){
memset(dp,0,sizeof(dp));
scanf("%d%d",&n,&m);
for(int i=0;i<n;++i){
Tree[i].clear();
scanf("%I64d%d",val+i,vid+i);
par[i]=i;
if(vid[i])
for(int j=1; j<=m; ++j)
dp[0][i][j]=dp[1][i][j]=val[i];
else
for(int j=0; j<=m; ++j)
dp[0][i][j]=val[i];
}
for(int i=1;i<n;++i){
int a,b; scanf("%d%d",&a,&b);
Tree[a].push_back(b);
Tree[b].push_back(a);
}
ans=0LL;
DFS(0);
DFS_DP(0);
printf("%I64d\n",ans);
}
return 0;
}
二、從上往下搜（參考神牛代碼寫的）
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
const int maxn=55555;
int n,m;
int val[maxn],vid[maxn];
int up[2][maxn][4];
int dp[2][maxn][4];
vector<int>G[maxn];
void DFS(int cnt,int fa){
up[0][cnt][0]=dp[0][cnt][0]=val[cnt];
if(val[cnt]) up[1][cnt][1]=dp[1][cnt][1]=val[cnt];
if(fa!=-1){
for(int i=0;i<=m;++i){
if(i!=m&&(up[0][fa][i]||dp[0][fa][i]))
dp[0][cnt][i+vid[cnt]]=max(dp[0][fa][i],up[0][fa][i])+val[cnt];
if(i==m&&vid[cnt]) continue;
if(dp[1][fa][i]||up[1][fa][i])
dp[1][cnt][i+vid[cnt]]=max(dp[1][fa][i],up[1][fa][i])+val[cnt];
}
}
int len=G[cnt].size();
for(int i=0;i<len;++i){
int son=G[cnt][i];
if(son==fa) continue;
DFS(son,cnt);
for(int j=0;j<=m;++j){
if(j!=m&&up[0][son][j])
up[0][cnt][j+vid[cnt]]=max(up[0][cnt][j+vid[cnt]],up[0][son][j]+val[cnt]);
if(j==m&&vid[cnt]) continue;
if(up[1][son][j])
up[1][cnt][j+vid[cnt]]=max(up[1][cnt][j+vid[cnt]],up[1][son][j]+val[cnt]);
}
}
}
int main(){
int T; scanf("%d",&T);
while(T--){
memset(dp,0,sizeof(dp));
memset(up,0,sizeof(up));
scanf("%d%d",&n,&m);
for(int i=0;i<n;++i)
scanf("%d%d",val+i,vid+i), G[i].clear();
for(int i=1;i<n;++i){
int a,b; scanf("%d%d",&a,&b);
G[a].push_back(b);
G[b].push_back(a);
}
DFS(0,-1);
int ans=0;
for(int i=0;i<n;++i)
for(int j=0;j<=m;++j)
ans=max(ans,max(dp[0][i][j],dp[1][i][j]));
printf("%d\n",ans);
}
return 0;
}
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
const int maxn=55555;
int n,m;
int val[maxn],vid[maxn];
int up[2][maxn][4];
int dp[2][maxn][4];
vector<int>G[maxn];
void DFS(int cnt,int fa){
up[0][cnt][0]=dp[0][cnt][0]=val[cnt];
if(val[cnt]) up[1][cnt][1]=dp[1][cnt][1]=val[cnt];
if(fa!=-1){
for(int i=0;i<=m;++i){
if(i!=m&&(up[0][fa][i]||dp[0][fa][i]))
dp[0][cnt][i+vid[cnt]]=max(dp[0][fa][i],up[0][fa][i])+val[cnt];
if(i==m&&vid[cnt]) continue;
if(dp[1][fa][i]||up[1][fa][i])
dp[1][cnt][i+vid[cnt]]=max(dp[1][fa][i],up[1][fa][i])+val[cnt];
}
}
int len=G[cnt].size();
for(int i=0;i<len;++i){
int son=G[cnt][i];
if(son==fa) continue;
DFS(son,cnt);
for(int j=0;j<=m;++j){
if(j!=m&&up[0][son][j])
up[0][cnt][j+vid[cnt]]=max(up[0][cnt][j+vid[cnt]],up[0][son][j]+val[cnt]);
if(j==m&&vid[cnt]) continue;
if(up[1][son][j])
up[1][cnt][j+vid[cnt]]=max(up[1][cnt][j+vid[cnt]],up[1][son][j]+val[cnt]);
}
}
}
int main(){
int T; scanf("%d",&T);
while(T--){
memset(dp,0,sizeof(dp));
memset(up,0,sizeof(up));
scanf("%d%d",&n,&m);
for(int i=0;i<n;++i)
scanf("%d%d",val+i,vid+i), G[i].clear();
for(int i=1;i<n;++i){
int a,b; scanf("%d%d",&a,&b);
G[a].push_back(b);
G[b].push_back(a);
}
DFS(0,-1);
int ans=0;
for(int i=0;i<n;++i)
for(int j=0;j<=m;++j)
ans=max(ans,max(dp[0][i][j],dp[1][i][j]));
printf("%d\n",ans);
}
return 0;
}
