【题目】

【题意】给定n个点的带边权树，要求将k个点染成黑色，使得 [ 黑点的两两距离和+白点的两两距离和 ] 最大。n<=2000。

【算法】树上背包

【题解】设f[i][j]表示子树i中有j个黑点对答案的贡献（包括点 i 到父亲的边 p ），由于边p的贡献只和 j 有关，所以最后再统计。

所以做树上背包即可，注意这题特殊在f[x][0]≠0，所以初始f[x][k]+=f[y][0]，然后不要把0作为物品。

最后统计边p的贡献：w[p] *（子树内黑点*子树外黑点+子树内白点*子树外白点）。

常数问题：要尽可能避免枚举无用状态，不然常数太大了，优化见代码。

#include
      
       #include
       
        #include
        
         #define ll long longusing namespace std;const int maxn=2010,inf=0x3f3f3f3f;struct edge{
    int v,w,from;}e[maxn*2];int first[maxn],tot,n,K,sz[maxn];ll f[maxn][maxn];void insert(int u,int v,int w){tot++;e[tot].v=v;e[tot].w=w;e[tot].from=first[u];first[u]=tot;}ll max(ll a,ll b){
     return a
         
          =0;k--){            f[x][k]+=f[e[i].v][0];//            for(int j=min(k,sz[e[i].v]);j>=1;j--)if(f[x][k-j]>-inf){
    //                f[x][k]=max(f[x][k],f[x][k-j]+f[e[i].v][j]);            }else break;        }    }    for(int i=0;i<=K;i++)if(f[x][i]>-inf)f[x][i]+=1ll*w*(1ll*i*(K-i)+1ll*(sz[x]-i)*(n-K-sz[x]+i));}int main(){    scanf("%d%d",&n,&K);    for(int i=1;i