LibreOJ 2124 「HAOI2015」树上染色

发表于 | 分类于 |

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

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

代码： 

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]);
}