本文共 1616 字，大约阅读时间需要 5 分钟。

链接：https://ac.nowcoder.com/acm/problem/19996

来源：牛客网

题目描述

有一棵点数为N的树，树边有边权。给你一个在0~N之内的正整数K，你要在这棵树中选择K个点，将其染成黑色，并将其他的N-K个点染成白色。 将所有点染色后，你会获得黑点两两之间的距离加上白点两两之间距离的和的收益。问收益最大值是多少。 输入描述: 第一行两个整数N,K。 接下来N-1行每行三个正整数fr,to,dis，表示该树中存在一条长度为dis的边(fr,to)。 输入保证所有点之间是联通的。N ≤ 2000,0 ≤ K ≤ N 输出描述: 输出一个正整数，表示收益的最大值。 示例1 输入 复制 5 2 1 2 3 1 5 1 2 3 1 2 4 2 输出 复制 17 说明 【样例解释】 将点1,2染黑就能获得最大收益。 这种题目一看就是枚举每条边的贡献。通过这道题目接触了树形背包。。 dp[i][j]表示着以i为根的子树中有j个点染成黑色的最大价值。 子树中的每个点都有两种状态，染色或者是不染色。所以类似于01背包。 代码如下：

#include
   
    #define ll long long#define inf 0x7f7f7f7fusing namespace std;const int maxx=2e3+100;struct edge{
   	int to,next;	ll w;}e[maxx<<1];int head[maxx<<1],tot,size[maxx];ll dp[maxx][maxx];int n,k;/*-------------事前准备-------------*/inline void init(){
   	memset(head,-1,sizeof(head));	for(int i=0;i<=n;i++)	for(int j=0;j<=n;j++) dp[i][j]=-inf;//初始化为负无穷大，	tot=0;}inline void add(int u,int v,ll w){
   	e[tot].to=v,e[tot].next=head[u],e[tot].w=w,head[u]=tot++;}/*------------树形dp-------------*/inline void dfs(int u,int f){
   	size[u]=1;	dp[u][0]=dp[u][1]=0;	ll ans;	for(int i=head[u];i!=-1;i=e[i].next)	{
   		int to=e[i].to;		ll w=e[i].w;		if(to==f) continue;		dfs(to,u);		size[u]+=size[to]; 		for(int j=size[u];j>=0;j--)//树形背包的模板，枚举以u为根的子树中染j个结点的最大值		{
   			for(int K=0;K<=size[to]&&K<=j;K++)//这j个结点中有K个在以to为节点的子树中			{
   				ans=(ll)(K)*(k-K)+(ll)(size[to]-K)*(ll)((n-size[to]-k+K));				ans*=w;				ans+=dp[to][K];//还要加上子树中已经染了K个结点的情况				dp[u][j]=max(dp[u][j],dp[u][j-K]+ans);//状态转移方程：dp[u][j]和dp[u][j-K]+ans比较。			}		}	}}int main(){
   	int x,y;ll w;	while(~scanf("%d%d",&n,&k))	{
   		init();		for(int i=1;i
   

努力加油a啊，(^o)/~

转载地址：http://wutvi.baihongyu.com/