[HAOI2015]树上染色

标签： 动态规划 树形结构 树形DP

---

题目描述

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

输入输出格式

输入格式

第一行包含两个整数 N, K 。接下来 N-1 行每行三个正整数 fr, to, dis ， 表示该树中存在一条长度为 dis 的边 (fr, to) 。输入保证所有点之间是联通的。

输出格式

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

输入输出样例

输入样例#1：
3 1
1 2 1
1 3 2
输出样例#1：
3

说明

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

题解

此题乍一看似乎不像一般tree dp的套路，因为当这个节点染色以后，会产生与其他节点的作用。
很容易想到的方程：dp[i][j]表示节点为i时，以i为根染j个节点为白色的最大值。但是我们这样设方程无法计算以i为根以外产生的贡献。所以我们要换个角度，从“大局”出发
设dp[i][j]表示节点为i时，以i为根染j个节点为白色的对答案的最大贡献，就是考虑节点i与儿子直接相连的边产生的贡献+儿子产生的贡献。
那么转移方程也就可以得到了：

ll w = e[i].w * (k * (m - k) + (son[e[i].to] - k) * (n - m - son[e[i].to] + k));
f[x][j] = max(f[x][j], f[x][j - k] + f[e[i].to][k] + w);

就是以边为对象，分别计算对黑色和白色产生的贡献

代码

#include<bits/stdc++.h>
#define N 2010
#define ll long long
using namespace std;

int n, m, x, y, k = 0;
int son[N], head[N];
ll  f[N][N], z;
struct node{int to, next; ll w;}e[N * 2];

void add(int u, int v, ll w)
{
    e[++ k].next = head[u]; e[k].to= v;
    e[k].w = w; head[u] = k;
}

void ss(int x, int fa)
{
    son[x] = 1;
    for(int i = head[x]; i; i = e[i].next)
        if(e[i].to != fa)
           ss(e[i].to, x), son[x] += son[e[i].to];
}

void dfs(int x, int fa)
{
    f[x][0] = f[x][1] = 0;
    for(int i = head[x]; i; i = e[i].next)
        if(e[i].to != fa)
        {
            dfs(e[i].to, x); 
            for(int j = min(m, son[x]); j >= 0; j --)
                for(int t = min(j, son[e[i].to]), k = 0; k <= t; k ++) //注意k的枚举顺序需要为正序，否则会使得f[x][j]有初值 
                {
                    ll w = e[i].w * (k * (m - k) + (son[e[i].to] - k) * (n - m - son[e[i].to] + k));
                    f[x][j] = max(f[x][j], f[x][j - k] + f[e[i].to][k] + w);
                }
        }
}

int main()
{
    memset(f, -0x7f7f7f, sizeof(f)); //需要有这个初始化，因为此题由于状态转移的特殊，不能使用未被更新的状态 
    scanf("%d%d", &n, &m);
    for(int i = 1; i < n; i ++)
    {
        scanf("%d%d%lld", &x, &y, &z);
        add(x, y, z); add(y, x, z);
    } 
    ss(1, -1); dfs(1, -1);
    printf("%lld", f[1][m]);
    return 0;
}

心得

如果从常用套路得不到答案时，往往可以换一个角度思考，大胆假设一种全新的方程定义。