dp在树上树形dp

P2014

int dfs(int cur){
    int s=1;
    dp[cur][1]=sc[cur];
    for(auto t:to[cur]){
        int siz=dfs(t);
        for(int i=min(s,m+1);i>=1;i--)
            for(int j=1;j<=siz&&i+j<=m+1;j++)
                dp[cur][i+j]=max(dp[cur][i+j],dp[cur][i]+dp[t][j]);
        s+=siz;
    }
    return s;
}

本来不想写这篇笔记的，但是做到P4362时深感自己功力不足，于是重新来复盘
这道题的 dp 数组[x][y]，x记录的是节点，而y记录的是x的子节点的价值（包括自己），这样避免了对每一个子节点都枚举物品数量。