LibreOJ 2124.「HAOI2015」树上染色

发现如果直接拿子问题 DP 是没法做的。
注意到问题相当于每条边两侧的同色点对之和,故可考虑对每条边统计贡献。

fu,if_{u,i} 表示在以 uu 为根的子树内选择 ii 个黑点的最大贡献
则转移时类似一个背包。
(题目似乎也不是很难)

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 2e3;
int n,m;
int to[N * 2 + 5],pre[N * 2 + 5],first[N + 5];
long long val[N * 2 + 5];
inline void add(int u,int v,long long w)
{
static int tot = 0;
to[++tot] = v,val[tot] = w,pre[tot] = first[u],first[u] = tot;
}
int fa[N + 5],sz[N + 5];
long long f[N + 5][N + 5];
void dfs(int p)
{
sz[p] = 1,f[p][0] = f[p][1] = 0;
for(register int i = first[p];i;i = pre[i])
if(to[i] ^ fa[p])
{
fa[to[i]] = p,dfs(to[i]),sz[p] += sz[to[i]];
for(register int j = min(sz[p],m);~j;--j)
for(register int k = 0;k <= min(min(sz[to[i]],m),j);++k)
f[p][j] = max(f[p][j],f[p][j - k] + f[to[i]][k] +
val[i] * ((long long)(m - k) * k + (long long)(n - sz[to[i]] - m + k) * (sz[to[i]] - k)));
}
}
int main()
{
memset(f,-0x3f,sizeof f);
scanf("%d%d",&n,&m);
int u,v;
long long w;
for(register int i = 1;i < n;++i)
scanf("%d%d%lld",&u,&v,&w),add(u,v,w),add(v,u,w);
dfs(1);
printf("%lld\n",f[1][m]);
}