【提高1课内 树形DP、换根】【2. 黑白树】

问题讨论区 提高段
,
1
题面

image
image715×557 27 KB

image
image
image139×775 3.92 KB

image

#include<bits/stdc++.h>
using namespace std;
struct edge
{
	int v,w;
};
int n,m;
int sz[2005];
bool is[2005];
vector<edge> g[2005];
int f[2005][2005]; //以i为根节点的子树 其中j个红色点 最大距离和 
void dfs(int x,int fa)
{
	sz[x]=1;
	for(int i=0;i<g[x].size();i++)
	{
		int v=g[x][i].v,w=g[x][i].w;
		if(v==fa) continue;
		dfs(v,x);
		for(int j=m;j>=0;j--) //枚举红色点个数 
		{
			f[x][j]=f[x][j]+sz[v]*(n-m)*w; //k=0的特判 
			for(int k=1;k<=j;k++) //枚举分配到 v下的红色点个数 
				f[x][j]=max(f[x][j],f[x][j-k]+f[v][k]+k*(m-k)*w+(sz[v]-k)*(n-m+k)*w);
		}
		sz[x]+=sz[v];
	}
}
int main()
{
	cin >> n >> m;
	for(int i=1;i<n;i++)
	{
		int u,v,w;
		cin >> u >> v >> w;
		g[u].push_back({v,w});
		g[v].push_back({u,w});
		is[v]=1;
	}
	int rt=-1; //寻找根节点 
	for(int i=1;i<=n;i++)
	{
		if(!is[i])
		{
			rt=i;
			break;
		}
	}
	dfs(rt,0);
//	for(int i=1;i<=n;i++) cout << sz[i] << " ";
//	cout << "\n";
//	for(int i=1;i<=n;i++)
//	{
//		for(int j=0;j<=m;j++)
//			cout << f[i][j] << " ";
//		cout << "\n";
//	}
	cout << f[rt][m];
    return 0;
}

WA(#1~5)+TLE(#6~10)，求调

2

捞

3

枚举j的时候要倒序枚举
式子也不对，式子应该是f[ x][j] = max(f[ x][j], f[ x][j-k] + f[y][k] + w * (k * (m - k) + (sz[v] - k) * (n - m - sz[v] + k)))

4

j本来就是倒序的呀
所以改成这样吗

void dfs(int x,int fa)
{
	sz[x]=1;
	for(int i=0;i<g[x].size();i++)
	{
		int v=g[x][i].v,w=g[x][i].w;
		if(v==fa) continue;
		dfs(v,x);
		for(int j=m;j>=0;j--) //枚举红色点个数 
		{
			//f[x][j]=f[x][j]+sz[v]*(n-m)*w; //k=0的特判 
			for(int k=0;k<=j;k++) //枚举分配到 v下的红色点个数 
				f[x][j]=max(f[x][j],f[x][j-k]+f[v][k]+1ll*k*(m-k)*w+1ll*w*(sz[v]-k)*(n-m-sz[v]+k));
		}
		sz[x]+=sz[v];
	}
}

WA+TLE 20分

5 
for(int j=m;j>=0;j--) //枚举红色点个数 
{
	for(int k=j;k>=1;k--) //枚举分配到 v下的红色点个数 
		f[x][j]=max(f[x][j],f[x][j-k]+f[v][k]+1ll*k*(m-k)*w+1ll*w*(sz[v]-k)*(n-m-sz[v]+k));
	f[x][j]=f[x][j]+sz[v]*(n-m-sz[v])*w; //k=0的特判 
}

样例输出20

6
  1. 填表改成刷表
  2. k倒叙枚举，k=0的特判放在最后
  3. k=0的特判少了一个f[v][0]
  4. f数组开long long

@栗子酱 关帖谢谢 :pray:

7

注意： 不开 long long 见祖宗

别问我怎么知道的，调了一天

8