P2014

P2014

题意

• 从一棵树中选择m条与根节点直接/间接相连的点,使得总权值最大

DP(树上背包)

状态: \(dp[i][j]\)表示在以\(i\)为根的子树中,选择了\(j\)个点的权值最大值

转移

• 选择第k个点:\(dp[i][j]=dp[i][j-k]+dp[to][k]\)
• 不选第k个点:\(dp[i][j]=dp[i][j]\)

决策:\(dp[i][j]=max(dp[i][j],dp[i][j-k]+dp[to][k])\)

细节

• \(k=0\)时没有父亲->把0作为根节点,从\(0\)开始DFS
• 因为多加了一个\(0\)节点,所以边数\(m\)要\(+1\)

代码

#include <bits/stdc++.h>
using namespace std;

int n,m;
int dp[310][310];
int s,k;
struct edge{
    int to,next;
}edge[310];
int head[310],cnt;

void insert(int from,int to){
    edge[++cnt].to=to;
    edge[cnt].next=head[from];
    head[from]=cnt;
}

void DFS(int x){
    for(int i=head[x];i;i=edge[i].next){
        int to=edge[i].to;
        DFS(to);
        //转化成01背包:背包大小为m,物品大小为k
        for(int j=m;j>0;j--){   //想要到达x的儿子必须走x,所以不存在不选x而选x的儿子,即j不为0
            for(int k=0;k<j;k++){   //j-k不为0(理由同上),所以k<j而不是k<=j
                dp[x][j]=max(dp[x][j],dp[x][j-k]+dp[to][k]);
            }
        }
    }
}

int main(){
    // freopen("1.in","r",stdin);
    cin>>n>>m;
    m++;
    for(int i=1;i<=n;i++){
        cin>>s>>dp[i][1];   //必须选自己
        insert(s,i);
    }
    DFS(0);
    cout<<dp[0][m]<<"\n";
}