题解 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为根的子树的节点数量 ```cpp #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; } ```