[HAOI2015] 树上染色（树形 DP）

题目传送门https://www.luogu.com.cn/problem/P3177

解题思路

设  表示以  为根的子树染  个黑点的最大收益值。

设一共有  个节点，要染  个点。

完成 DP 状态的设计后，开始推导转移方程……

对于一个点 ，它下面有一条通向 ，权值为  的边。

我们枚举 ，表示以  为根的子树已经染了  个点；

然后在枚举  表示以  为子树要染  个点；

然后，这条边的贡献会是多少呢？

首先，如果  为根的子树有  个被染的点，那么是不是  以外应该会有  个点，然后两边的点两两组合，得到的贡献是 。

然后，如果  为根的子树有  个被染的点，那么是不是  为根的子树就会有  个白点？对于  以外，应该会有  个白点。同理，两两组合，贡献是：。

（其中  表示  为根的子树的大小）。

于是，我们可以从 1 号点开始 dfs，同时进行 DP。

代码

记得开 long long！

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m;
vector<pair<int,int> > g[2001];
int size[2001];
int f[2001][2001];

void dfs(int x,int fa)
{
	size[x]=1;
	for(auto y:g[x])
	{
		int to=y.first;
		int w=y.second;
		if(to==fa)continue;
		
		dfs(to,x);
		
		for(int j=min(m,size[x]);j>=0;j--)
		{
			for(int k=min(m,size[to]);k>=0;k--)
			{
				if(j+k<=m)
				{
					int temp;
					temp=k*(m-k)*w+(size[to]-k)*(n-m-(size[to]-k))*w;
					f[x][j+k]=max(f[x][j+k],f[x][j]+f[to][k]+temp);
				}
			}
		}
		
		size[x]+=size[to];
	}
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin>>n>>m;
	
	int u,v,w;
	for(int i=1;i<=n-1;i++)
	{
		cin>>u>>v>>w;
		g[u].push_back(make_pair(v,w));
		g[v].push_back(make_pair(u,w));
	}
	
	dfs(1,0);
	
	cout<<f[1][m];
	return 0;
}