1 条题解
-
0
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; }
- 1
信息
- ID
- 241
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- 6
- 标签
- 递交数
- 24
- 已通过
- 11
- 上传者