78分求助!!!
查看原帖
78分求助!!!
320449
forest114514楼主2023/7/13 16:45

我真的不知道怎么改了

//蒟蒻一枚
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=150;
struct mp{
	int re,ne,num;
}s[N*2];
int idx=0,head[N];
int n,q,son[N][2],to[N][2],d[N];
int f[N][N];
bool b[N];
void _add(int u,int v,int w){
	s[++idx].re=v;
	s[idx].num=w;
	s[idx].ne=head[u];
	head[u]=idx;
}
void build(int temp){
	if(d[temp]==1||b[temp]) return;
	b[temp]=1;
	int cnt=0;
	for(int i=head[temp];i;i=s[i].ne){
		if(b[s[i].re]==0){
			son[temp][cnt]=i;
			to[temp][cnt++]=s[i].re;
		}
	}
	build(to[temp][0]);
	build(to[temp][1]);
}
void dfs(int i,int j){
	if(!i||j>=q||j<0||f[i][j]!=0) return;
	
	int li=to[i][0],ri=to[i][1];
	int sli=s[son[i][0]].num,sri=s[son[i][1]].num;
	dfs(li,j-1);
	f[i][j]=max(f[i][j],f[li][j-1]+sli);
	dfs(ri,j-1);
	f[i][j]=max(f[i][j],f[ri][j-1]+sri);
	
	for(int k=j-2;k>=0;--k){
		dfs(ri,j-k-2);dfs(li,k);
		f[i][j]=max(f[i][j],f[li][k]+f[ri][j-k-2]+sli+sri);
	}
}
int main(){
	//ios::sync_with_stdio(false);
	cin>>n>>q;
	int u,v,w;
	for(int i=1;i<=n-1;i++){
		cin>>u>>v>>w;
		_add(u,v,w);
		_add(v,u,w);
		d[u]++,d[v]++;
	}
	int fa;
	for(int i=1;i<=n;i++) if(d[i]==2){fa=i;break;}
	build(fa);
	//for(int i=1;i<=n;i++)cout<<to[i][0]<<" "<<to[i][1]<<endl;
	dfs(fa,q-1);
	cout<<f[fa][q-1]<<endl;
	return 0;
}

大佬们能帮忙看一下哪里有问题吗(Orz)

2023/7/13 16:45
加载中...