夏晓光(loveJY)的博客

“将我大汉军旗插遍大漠草原！”

封面图小姐姐好色气啊

及树上DP的一些总结qwq

首先说说这个题,dp[i][j]表示点i的子树里选了j个黑点目前得到的最大贡献是什么

贡献是指i子树里所有边的贡献,转移时考虑i到v这条边的贡献,两侧共有多少个黑白点乘一下就好啦

然后这样子好像再套个树形背包就解决了!

下面说下树形DP的坑点

1. 转移时,我们枚举要从大到小枚举,第一重循环不这样做会导致完全背包,第二重循环不这样做如果循环内有0(比如这题0个黑点情况)就会导致先更新后又更新

2. $siz[u]+=siz[v]$要之后加,否则一条链就卡掉了

别的好像没啥了

再说下树的直径?

dp[u]表示点u最长链

当发现dp[v]+1>dp[u]时,我们先把这两条链拼起来更新答案再update u

别的没了qwq可能还有什么树上容斥?没做啊

code:

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define int long long
const int MAXN = 3500;

int n, M, ccnt, N;
int dp[MAXN][MAXN], siz[MAXN];
int home[MAXN * 2], nxt[MAXN * 2], to[MAXN * 2], len[MAXN * 2];

inline void ct(int x, int y, int z) {
	ccnt++;
	nxt[ccnt] = home[x];
	to[ccnt] = y;
	home[x] = ccnt;
	len[ccnt] = z;
}

inline void dfs(int u, int F) {
	siz[u] = 1;
	for(int i = home[u], val; i; i = nxt[i]) {
		int v = to[i];
		if(v == F)continue;
		dfs(v, u);
		for(int j = min(M, siz[u]); j >= 0; --j) {
			for(int k = min(M, siz[v]); k >= 0; --k) {
				val = len[i] * k * (M - k) + len[i] * (siz[v] - k) * (N - siz[v] + k);
				dp[u][j + k] = max(dp[u][j + k], dp[u][j] + dp[v][k] + val);
			}
		}
		siz[u] += siz[v];
	}
	return ;
}


signed main() {
	scanf("%lld%lld", &n, &M);
	N = n - M;
	for(int i = 2, x, y, z; i <= n; ++i) {
		scanf("%lld%lld%lld", &x, &y, &z);
		ct(x, y, z);
		ct(y, x, z);
	}
	dfs(1, 0);
	printf("%lld\n", dp[1][M]);
	return 0;
}