[HAOI2015]树上染色

树形背包dp，求整体贡献。

别的树形dp一般是考虑子树的最优解，但这道题由于每次转移都会对全局提供贡献，所以我们考虑贡献。令dp[i][j]表示以i为根的子树选j个点最多能为最终答案做的贡献。那么这道题就转化为了树形背包dp，转移方程：

	int tmp = k*(m-k)*w + (size[v]-k)*(n-m+k-size[v])*w;（求一条边对答案的贡献）
        dp[s][j]=max(dp[s][j],dp[s][j-k]+dp[v][k]+tmp);(背包的转移，不过权值换为了对答案的贡献)

注意特判 if (dp[s][j-k]==-1) continue;

code

#include<iostream>
#include<cstdio>
#include<queue>
#include<algorithm>
#include<cstring>
#include<stack>
#include<bitset>
#include<cmath>
#define int long long 
using namespace std;
const int maxn=2006;
const int k=2333;
struct hzw
{
  int to,next,v;
}e[maxn*2];
int head[maxn*2],cur,val[maxn];
inline void add(int a,int b,int c)
{
	e[cur].to=b;
	e[cur].next=head[a];
	e[cur].v=c;
	head[a]=cur++;
}
int dp[3001][3001],n,m,size[maxn];
inline void dfs(int s,int fa)
{
    for (int i=0;i<=m;++i) dp[s][i]=-1;
    dp[s][0]=dp[s][1]=0;
    size[s]=1;
    for (int i=head[s];i!=-1;i=e[i].next)
    {
        if (e[i].to==fa) continue;
        dfs(e[i].to,s);
        size[s]+=size[e[i].to];
    }
    for (int i=head[s];i!=-1;i=e[i].next)
    {
        int v=e[i].to,w=e[i].v;
        if (v==fa) continue;
        for (int j=min(size[s],m);j>=0;j--)
            for (int k=0;k<=min(j,size[v]);++k)
            {
            	if (dp[s][j-k]==-1) continue;
        		int tmp = k*(m-k)*w + (size[v]-k)*(n-m+k-size[v])*w;
                dp[s][j]=max(dp[s][j],dp[s][j-k]+dp[v][k]+tmp);
            } 
    }
}
signed main()
{ 
	memset(head,-1,sizeof(head));
    cin>>n>>m;
    for (int i=1,a,b,c;i<=n-1;++i)
    {
        scanf("%lld%lld%lld",&a,&b,&c);
//        cout<<a<<" "<<b<<" "<<c<<"shit"<<endl;
        add(a,b,c);
        add(b,a,c);
    }
    dfs(1,1);
    cout<<dp[1][m];
}

收获：

1、树形背包问题的常见转移套路。
2、如果改变状态会对整体答案造成影响，考虑转移对答案的贡献。