P3177 [HAOI2015] 树上染色
2026-05-07
题目大意
给定一棵 n 个结点的树选取 m 个点进行黑白染色,求黑白两两之间距离和的最大值。
题解
显然 DP 状态为 f[u][j] 表示节点 u 内选 j 个黑点能得到的距离和最大值。
那么如何转移?显然直接转移对于两两距离和不好求,考虑计算一条边的贡献,设当前节点为 u,当前处理的儿子为 v,在 u 和 v 中选取 j 个黑点,在 v 中选取 k 个黑点,那么黑点经过这条边的次数为 (m−k)×k,同理白点经过次数为 (n−m−sizev+k)×(sizev−k)(注意这里是全局的 n 和 m,因为需要考虑一条边的所有贡献),容易写出状态转移方程:
f[u][j]=kmax{f[u][j−k]+f[v][k]+w×((m−k)×k+(n−m−sizev+k)×(sizev−k))}
接下来处理边界情况,显然对于叶子节点 f[u][0]=f[u][1]=0,对于非叶子节点也有 f[u][0]=f[u][1]=0(此时相当于一个子节点都没有合并)。
其实还有 k 的边界问题,显然上界是 min(j,sizev),而下界则要考虑 u 子树中能否取 j−k 个黑点,下界即为 max(0,j−siz[u])。
代码
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
typedef long long LL;
const int N = 2e3+10 , M = N*2;
int n , m;
int h[N] , e[M] , ne[M] , w[M] , idx;
int siz[N];
LL f[N][N];
void add(int a , int b , int c) {
w[idx] = c , e[idx] = b , ne[idx] = h[a] , h[a] = idx ++;
}
void dfs(int u , int p) {
siz[u] = 1; f[u][0] = f[u][1] = 0;
for(int i = h[u] ; ~i ; i = ne[i]) {
int v = e[i];
if(v == p) continue;
dfs(v , u);
for(int j = min(siz[u]+siz[v] , m) ; j >= 0 ; j --) {
for(int k = max(j-siz[u] , 0) ; k <= min(j , siz[v]) ; k ++) {
f[u][j] = max(f[u][j] , f[u][j-k]+f[v][k]+1ll*w[i]*k*(m-k)+1ll*w[i]*(n-m-siz[v]+k)*(siz[v]-k));
}
}
siz[u] += siz[v];
}
}
int main() {
scanf("%d%d" , &n , &m);
memset(h , -1 , sizeof h);
for(int i = 1 ; i < n ; i ++) {
int a , b , c;
scanf("%d%d%d" , &a , &b , &c);
add(a , b , c);
add(b , a , c);
}
memset(f , 0xc0 , sizeof f);
dfs(1 , -1);
printf("%lld\n" , f[1][m]);
return 0;
}