30分wa求调
查看原帖
30分wa求调
929424
qiyuang楼主2025/6/17 21:45
#include<bits/stdc++.h>
using namespace std;
int n,k,head[2005],cnt,f[2005][2005],size[2005],u,v,w;
struct node{
	int v,w,ne;
}e[5005];
void add(int u,int v,int w){
	e[++cnt]={v,w,head[u]};
	head[u]=cnt;
}
void dfs(int u,int fa){
	size[u]=1;
	for(int i=head[u],v;i;i=e[i].ne){
		v=e[i].v;
		if(v==fa) continue;
		dfs(v,u);
		for(int x=size[u];x>=0;x--){
			for(int y=size[v];y>=0;y--){
				if(x+y>k) continue;
				int t=(y*(k-y))+((size[v]-y)*(n-k-size[v]+y));
				f[u][x+y]=max(f[u][x+y],f[u][x]+f[v][y]+e[i].w*t);
			}
		}
		size[u]+=size[v];
	}
}
int main(){
	cin>>n>>k;
	for(int i=1;i<n;i++){
		cin>>u>>v>>w;
		add(u,v,w);
	}
	dfs(1,0);
	cout<<f[1][k];
	return 0;
}

不知道哪里有问题,求大佬

2025/6/17 21:45
加载中...