BZOJ 4033 [HAOI2015]树上染色

有一棵点数为N的树，树边有边权。给你一个在0~N之内的正整数K，你要在这棵树中选择K个点，将其染成黑色，并
将其他的N-K个点染成白色。将所有点染色后，你会获得黑点两两之间的距离加上白点两两之间距离的和的收益。

问收益最大值是多少。

设dp[i][j]为以i为子树，染j个黑点对全局的贡献

dp[i][j]=dp[i][j-t]+dp[e][t]+cost

cost考虑i的儿子对i的连边的贡献,设边权为ev,儿子为son

cost=t_ev_(k-t)+(size[son]-t)*(n-size[son]-k+t)

特别值得注意的是，该状态设定时就是考虑对全局的贡献，而不是对以i为根的子树的贡献

CODE:

\#include<bits/stdc++.h>
#define ll long long 
struct edge{
    int to,next;ll v;
}e[5000];
inline ll read(){;

    ll x=0,flag=1;//
    scanf("%lld",&x);
    return x;char c=getchar();
    while(!isdigit(c)){if(c=='-')flag*=-1;c=getchar();}
    while(isdigit(c)){x=1ll*(x<<3)+1ll*(x<<1)+c-'0';c=getchar();}
    return flag*x;
}
int cnt=0,last[4000],size[4000],n,k;
ll dp[2010][2010];
inline void add(int a,int b,ll c){
    cnt++;
    e[cnt].next=last[a],last[a]=cnt;
    e[cnt].to=b,e[cnt].v=c;
}
inline void dfs(int x,int fa){
    size[x]=1;
    dp[x][1]=dp[x][0]=0;
    for(int i=last[x];i;i=e[i].next){
        if(e[i].to==fa) continue;
        dfs(e[i].to,x);
        size[x]+=size[e[i].to];
    }
    for(int i=last[x];i;i=e[i].next){
        if(e[i].to==fa) continue;
        for(int j=std::min(k,size[x]);j>=0;--j){
            for(int t=0;t<=std::min(j,size[e[i].to]);++t)
                if(dp[x][j-t]!=-1){
                    dp[x][j]=std::max(dp[x][j],dp[x][j-t]+1ll*dp[e[i].to][t]+1ll*e[i].v*t*(k-t)+1ll*e[i].v*(n-k+t-size[e[i].to])*(size[e[i].to]-t));
                    //printf("%lld\n",+1ll*e[i].v*t*(k-t)+1ll*e[i].v*(n-k+t-size[e[i].to])*(size[e[i].to]-t));

                }
            }
    }
}
int main(){
    n=read(),k=read();
    for(int i=1;i<=n-1;++i){
        int a=read(),b=read(),c=read();
        add(a,b,c);
        add(b,a,c);
    }
    memset(dp,-1,sizeof(dp));
    dfs(1,0);
    printf("%lld",dp[1][k]);
    return 0;
}