2021.07.17 P3177 树上染色（树形DP）

2021.07.17 P3177 树上染色（树形DP）

[P3177 HAOI2015]树上染色 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

重点：

1.dp思想是需要什么，维护什么。

2.通过具体的状态推出未知状态的解法。

题意：

一棵有n个点的树，将其中k个点染为黑色，其余点为白色，求任意一对白白两点之间的距离和与任意一对黑黑两点之间的距离。

分析：

dp思想是需要什么，维护什么。我们需要求距离和，我们就维护距离和。

在已经确定哪些点是黑点是，对于一条边，它对答案的贡献是端点u、v两端是

\[（u黑点个数*v黑点个数+u白点个数*v白点个数）*这条边的权值
\]

但我们还不知道哪些点是黑点，所以我们也要列出不同黑点个数，进行状态转移。

设ans[i] [j]为在以i为根的子树中，有j个点是黑点时的总贡献，依次枚举i可能的黑点个数、i的每一个子节点、以该子节点为根的子树可能的黑点的个数进行状态转移。具体分析在代码中。

代码如下：

#include<cstdio>

#include<algorithm>

#include<iostream>

#include<cstring>

using namespace std;

#define int long long

const int N=2010;

int n,k,size[N],cnt,head[N],ans[N][N];

struct node{

	int to,next,val;

}a[N*2];

inline int read(){

	int s=0,w=1;

	char ch=getchar();

	while(ch<'0'||ch>'9'){

		if(ch=='-')w=-1;

		ch=getchar();

	}

	while(ch<='9'&&ch>='0'){

		s=s*10+ch-'0';

		ch=getchar();

	}

	return s*w;

}

void add(int u,int v,int w){

	++cnt;

	a[cnt].to=v;

	a[cnt].val=w;

	a[cnt].next=head[u];

	head[u]=cnt;

}

void dfs(int x,int fa){

	size[x]=1;

	ans[x][0]=ans[x][1]=0;

	for(int i=head[x];i;i=a[i].next){

		int v=a[i].to;

		if(v==fa)continue;

		dfs(v,x);

		size[x]+=size[v];

		for(int j=min(k,size[x]);j>=0;j--){

			if(ans[x][j]!=-1)

			ans[x][j]+=ans[v][0]+size[v]*(n-k-size[v])*a[i].val;//当以x为根的子树中黑点个数为0时的贡献

			for(int l=min(j,size[v]);l>0;l--){

				if(ans[x][j-l]==-1)continue;//当这个子树中黑点个数为j-l这一状态还没开始计算时，果断跳过

				ans[x][j]=max(ans[x][j],ans[x][j-l]+ans[v][l]+(l*(k-l)+(size[v]-l)*(n-k-size[v]+l))*a[i].val);//注意：计算的时候这条边会产生的贡献，以j为根节点的子树有l个黑点，所以这条边因为黑点产生的贡献为l*(k-l)*a[i].val，白点产生的贡献为(size[v]-l)*(n-k-size[v]+l)*a[i].val，而以x为根节点的子树此时有j-l个黑点，以v为根节点的子树有l个黑点

			}

		}

	}

}

signed main(){

	//freopen("1.in","r",stdin);

	//freopen("1.out.txt","w",stdout);

	n=read();k=read();

	if(n-k<k)k=n-k;

	for(int i=1;i<n;i++){

		int u,v,w;

		u=read();v=read();w=read();

		add(u,v,w);

		add(v,u,w);

	}

	memset(ans,-1,sizeof(ans));

	dfs(1,0);

	cout<<ans[1][k];

	return 0;

}

2021.07.17 P3177 树上染色（树形DP）的相关教程结束。