感觉是时候总结一下树形背包的题目了，虽然都是树形背包，但是不同题目细节却有着不小的区别，这里我由两道题来分析不同点（尤其是状态是否合法的考虑以及转移循环的范围限制，对于dp 范围的限制一直都算是一个细节考虑），一题是本题，还有一题是经典树上背包 ————选课

先上选课

https://www.luogu.com.cn/problem/P2014

• 这题不得了，算是板子和依赖背包转化 首先由于有依赖关系，转化为树形解决该问题，定义状态，dp[i][j][k]——以i节点为根的子树中到其第j个儿子处理完后，选了k个的最大收益 转移方程dp[i][j][k]=max(dp[i][j-1][k],dp[i][j-1][k-l]+dp[son][all][l])滚动数组倒叙后dp[i][j]=max(dp[i][j],dp[i][j-k]+dp[son][k])此处要注意j与k的取值范围(0<=j<=m,0<=k<j)k之所以小于k因为此树有依赖关系，如果儿子选，那么父亲一定要选 而对于状态的合法性则不需要特殊关照，因为dp[i][j]为以i为根节点的子树，选不少于j个点的最大收益， 相当于0/1背包 而对于下面有状态限制的题目，则相当于恰好装满的背包，必须严格对待状态的合法性

https://ac.nowcoder.com/acm/problem/19996

• 这题乃书上染色，属实不错的一题 首选拿到树题考虑能否dp... 一个dp发展选手的思维，是否满足递推性质，dp[i][j]以i为根节点的子树中选择j个涂黑，我们的决策是每个儿子选多少涂黑，来满足总收益最大，而总收益还可当前子树根节点上面的黑色结点位置有关——————————对于树的距离和问题，要思考到一个常用套路（每条边的贡献）故如果当前儿子下面选k个点涂黑，那么w[u][v]这条边的当前贡献就是w[u][v]k,且儿子边所有贡献翻倍,满足线性更新，故装一方程dp[i][j]=max(dp[i][j],dp[i][j-k]+dp[son][k]+calc(k,K-k,sz[son]-k,n-K-sz[son]+k,w[u][v]));讨论以下calc函数，此题贡献是黑点与白点 而状态中只保存了黑点，故需要完善保证无后效性 calc是当前边的贡献，是上边黑点与下边黑点，以及上边百点与下边百点有关总和计算 假设上面黑点有n个 下面黑点有m个 那么此边的贡献是nm

ll calc(int heix,int heis,int baix,int bais,int w){
	return (heix*heis+baix*bais)*w;
}

下面直接上代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e3+8;
const int inf = 0x3f3f3f3f;
ll n,k,dp[N][N],from,to,sz[N];
vector<pair<int,int> >e[N];
ll calc(ll heix,ll heis,ll baix,ll bais,ll w){
    return heix*heis*w+baix*bais*w;
}
void dfs(int cur,int fa){
    sz[cur]=1;
    dp[cur][0]=dp[cur][1]=0;
    for(int i=0;i<e[cur].size();i++){
        int now = e[cur][i].first;
        ll w = e[cur][i].second;
        if(now==fa)continue;
        dfs(now,cur);
        sz[cur]+=sz[now];
        for(ll j=min(k,sz[cur]);j>=0;j--)//以当前节点为根的树选了j个黑点的最大值
        {
            for(int q=0;q<=min(sz[now],j);q++)//儿子选多少个黑
            {
                dp[cur][j]=max(dp[cur][j],dp[cur][j-q]+dp[now][q]+calc(q,k-q,sz[now]-q,n-k+q-sz[now],w));
            }
        }
    }
}
ll w;
int main()
{
    cin>>n>>k;
    memset(dp,-inf,sizeof(dp));
    for(int i=1;i<=n-1;i++){
        cin>>from>>to>>w;
        e[from].push_back({to,w});
        e[to].push_back({from,w});
    }
    dfs(1,0);
    cout<<dp[1][k]<<endl;
    return 0;
}

dp[i][j]为以i为根节点的子树选了j个黑点，由于题目规定涂黑K个，故这是一个恰好装满的背包，所以所有有效状态必须由有效状态推出,将所有状态设为-inf,每次dfs更新初始状态(有效状态)dp[cur][0]=dp[cur][1]=0;