(树形DP) bzoj 4033

4033: [HAOI2015]T1

Time Limit: 10 Sec Memory Limit: 256 MB
Submit: 120 Solved: 57
[Submit][Status][Discuss]

Description

有一棵点数为 N 的树，树边有边权。给你一个在 0~ N 之内的正整

数 K ，你要在这棵树中选择 K个点，将其染成黑色，并将其他的

N-K个点染成白色。将所有点染色后，你会获得黑点两两之间的距

离加上白点两两之间的距离的和的受益。问受益最大值是多少。

Input

第一行包含两个整数 N, K 。

接下来 N-1 行每行三个正整数 fr, to, dis ，表示该树中存在一条长度

为 dis 的边 (fr, to) 。输入保证所有点之间是联通的。

Output

输出一个正整数，表示收益的最大值。

Sample Input

3 1
1 2 1
1 3 2

Sample Output

HINT

对于 100% 的数据， 0<=K<=N <=2000

dpi,j记录的就是，子树

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>
#include<algorithm>
#include<cstdlib>
#include<vector>
#define INF 100000000
using namespace std;
int n,k;
long long dp[2005][2005],siz[2005];
struct node
{
    int x,y,z;
    node(int _y,int _z) : y(_y),z(_z) {}
};
vector<node> e[2005];
void dfs(int u,int father)
{
    siz[u]=1;
    dp[u][0]=0;
    dp[u][1]=0;
    long long ans;
    for(int i=0;i<e[u].size();i++)
    {
        int v=e[u][i].y;
        int w=e[u][i].z;
        if(v==father)
            continue;
        dfs(v,u);
        siz[u]+=siz[v];
        for(int j=siz[u];j>=0;j--)
        {
            for(int kk=0;kk<=siz[v]&&kk<=j;kk++)
            {
                ans=(long long)kk*(k-kk)+(long long)((siz[v]-kk)*(n-k-(siz[v]-kk)));
                ans=(long long)(ans*w);
                ans+=dp[v][kk];
                dp[u][j]=max(dp[u][j],dp[u][j-kk]+ans);
            }
        }
    }
}
int main()
{
    scanf("%d%d",&n,&k);
    for(int i=1;i<n;i++)
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        e[x].push_back(node(y,z));
        e[y].push_back(node(x,z));
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
            dp[i][j]=-INF;
    }
    dfs(1,0);
    printf("%lld
",dp[1][k]);
    return 0;
}