记录编号	568308	评测结果	AAAAAAAAAA
题目名称	[HAOI 2015]树上染色	最终得分	100
用户昵称	ZRQ	是否通过	通过
代码语言	C++	运行时间	0.783 s
提交时间	2021-12-23 20:41:51	内存使用	36.47 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#define ll long long
using namespace std;
int n,m,head[2005],e[4005],nxt[4005],w[4005],cnt,siz[2005];
ll f[2005][2005];
char ch;
inline void read(int &x){x=0;ch=getchar();while(ch<48||ch>57)ch=getchar();while(ch>47&&ch<58)x=(x<<3)+(x<<1)+(ch^48),ch=getchar();}
inline void add(int x,int y,int z){nxt[++cnt]=head[x],head[x]=cnt,e[cnt]=y,w[cnt]=z;}
void DFS(int nw,int fa)
{
	siz[nw]=1; f[nw][0]=f[nw][1]=0;
	for(int i=head[nw];i;i=nxt[i])
	{
		if(e[i]==fa) continue;//防止重复 
		DFS(e[i],nw); siz[nw]+=siz[e[i]];
		for(int j=min(siz[nw],m);j>=0;--j)//最多染色j个点 
		{
			if(f[nw][j]!=-1) f[nw][j]+=f[e[i]][0]+(ll)siz[e[i]]*(n-m-siz[e[i]])*w[i];
			for(int k=min(j,siz[e[i]]);k;--k) if(f[nw][j-k]!=-1)  f[nw][j]=max(f[nw][j],f[nw][j-k]+f[e[i]][k]+(ll)(k*(m-k)+(siz[e[i]]-k)*(n-m-siz[e[i]]+k))*w[i]);
		}
	}
}
int main()
{
	freopen("haoi2015_t1.in","r",stdin);
	freopen("haoi2015_t1.out","w",stdout);
	int x,y,z;
	read(n),read(m); if(n-m<m) m=n-m; 
	for(int i=1;i<n;++i) read(x),read(y),read(z),add(x,y,z),add(y,x,z);
	memset(f,-1,sizeof(f));
	DFS(1,-1);
	printf("%lld\n",f[1][m]);
	return 0;
}