题解 P3177 【[HAOI2015]树上染色】

· · 题解

HAOI的题，写的人就是少，不过这确实是道好题，来顶一发

应该很容易想到，dp是可做的

状态很容易想到，dp[u][i]表示以u为跟的子树中，选择i个黑节点，的最大值

然后我就不会做了， 去网上看了wmdcstdio神犇的题解

发现我这个状态定义是错误的，正确的状态应该是，dp[u][i]表示以u为跟的子树中，选择i个黑节点，对答案有多少贡献

为什么是说“对答案有多少贡献呢”？

主要是想到一点，即分别考虑每条边对答案的贡献

即，边一侧的黑节点数*另一侧的黑节点数*边权+一侧的白节点数*另一侧的白节点数*边权

这点很容易证明，但是不容易想到（原因是我太弱了）

然后情况就明了了，整个问题成了一个树形背包，考虑每个子节点分配多少个黑色节点（体积），然后算出这条边对答案的贡献（价值）

这里再一次强调“贡献”，是因为这个贡献不只是在当前子树内，而是对于整棵树来说的

转移方程为dp[u][i] = max( dp[u][i], dp[u][i-j] + dp[v][j] + val )

其中v为u的子节点，j为在这个子节点中选择的黑色点的个数，val为这条边的贡献

val = j*(k-j)*w + (sz[v]-j)*(n-k+j-sz[v])*w

其中w为这条边的边权，n为总的节点数，k为总的需要选择的黑色节点数，sz[v]为以v为根的子树的节点数量

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <cmath>
using namespace std;
typedef long long ll;
const ll INFLL = 0x3f3f3f3f3f3f3f3f;
const int INF = 0x3f3f3f3f;
const int MAXN = 2010;
int n,k;
struct Tree {
    int head[MAXN], nxt[MAXN<<1], to[MAXN<<1], w[MAXN<<1], idx;
    Tree() { idx = 0; memset( head, -1, sizeof(head) ); }
    void addedge( int u, int v, int val ) {
        to[idx] = v; nxt[idx] = head[u]; w[idx] = val; head[u] = idx; ++idx;
        to[idx] = u; nxt[idx] = head[v]; w[idx] = val; head[v] = idx; ++idx;
    }
}tree;
ll dp[MAXN][MAXN]; int sz[MAXN];
void dfs( int u, int fa ) {
    sz[u] = 1; memset( dp[u], -1, sizeof(dp[u]) ); dp[u][0] = dp[u][1] = 0;
    for( int e = tree.head[u]; ~e; e = tree.nxt[e] ) {
        int v = tree.to[e]; if( v == fa ) continue; dfs(v,u); sz[u] += sz[v];
    }
    for( int e = tree.head[u]; ~e; e = tree.nxt[e] ) {
        int v = tree.to[e]; if( v == fa ) continue; int w = tree.w[e];
        for( int i = min(k,sz[u]); i >= 0; --i ) for( int j = 0; j <= min(i,sz[v]); ++j ) if( ~dp[u][i-j] ) {
            ll val = (ll)j*(k-j)*w + (ll)(sz[v]-j)*(n-k+j-sz[v])*w;
            dp[u][i] = max( dp[u][i], dp[u][i-j] + dp[v][j] + val );
        }
    }
}
int main() {
    scanf( "%d%d", &n, &k );
    for( int i = 0; i < n-1; ++i ) {
        int u,v,w; scanf( "%d%d%d", &u, &v, &w ); tree.addedge(u,v,w);
    } dfs(1,0); printf( "%lld\n", dp[1][k] );
    return 0;
}