记录编号	568305	评测结果	AAAAAAAAAA
题目名称	[HAOI 2015]树上染色	最终得分	100
用户昵称	遥时_彼方	是否通过	通过
代码语言	C++	运行时间	0.331 s
提交时间	2021-12-23 19:00:00	内存使用	67.13 MiB

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
using namespace std;
char ra;
inline void readl(ll &x)
{
	x&=0;
	ra=getchar();
	while(ra<'0'||ra>'9') ra=getchar();
	while(ra>='0'&&ra<='9') 
	{
		x=(x<<3)+(x<<1)+(ra^48);
		ra=getchar();
	}
} 
inline void read(int &x)
{
	x&=0;
	ra=getchar();
	while(ra<'0'||ra>'9') ra=getchar();
	while(ra>='0'&&ra<='9') 
	{
		x=(x<<3)+(x<<1)+(ra^48);
		ra=getchar();
	}
} 
inline void write(ll x)
{
	if(x/10) write(x/10);
	putchar(x%10+48);
}
///////////以上为快读快输 
const int N=2005;
ll nc,mc;
ll dis[N][N];//路径边权 
int st[N];
struct tre
{
	int ar;
	int nx;
}n[N<<1];
int nj;
inline void ADD(int &x,int &y)
{
	n[++nj].nx=st[x];
	n[nj].ar=y;
	st[x]=nj;
	return;
}
ll sz[N];//以各结点为根的子树大小 
ll f[N][N];//f[x][y]:给以x为根结点的树染上y个点所得的对于整棵树的最大贡献 
void dfs(int cl)
{
	sz[cl]++;
	f[cl][0]=f[cl][1]=0;/////子树大小必定大于等于1，因此该子树不染色或染一个点均为合法情况 
	for(int i1=st[cl],s1;i1;i1=n[i1].nx)
	{
		s1=n[i1].ar;
		if(sz[s1]) continue;///双向树，判定父亲并跳过 
		dfs(s1);//先处理子树 
		sz[cl]+=sz[s1];///更新子树大小 
		for(ll i2=min(mc,sz[cl]),mn;i2>=0;i2--)
		{
			mn=min(sz[s1],i2);
			for(ll i3=0,val;i3<=mn;i3++)
			{
				if(f[cl][i2-i3]==-1) continue;//跳过非法情况 
				val=dis[cl][s1]*(i3*(mc-i3)+(sz[s1]-i3)*(nc-sz[s1]+i3-mc));//该边对于整棵树的贡献 
				f[cl][i2]=max(f[cl][i2],f[cl][i2-i3]+f[s1][i3]+val);//二维背包，更新数值 
			}
		}
	}
	return;
}
int main()
{
	freopen("haoi2015_t1.in","r",stdin);
	freopen("haoi2015_t1.out","w",stdout);
    readl(nc);
    readl(mc);
    int s1,s2;
    ll s3;
    for(int i=1;i<nc;i++)
    {
    	read(s1);
    	read(s2);
    	readl(s3);
    	dis[s1][s2]=dis[s2][s1]=s3;
    	ADD(s1,s2);
    	ADD(s2,s1);
	}
	///////////以上为前向星建树过程 
	memset(f,-1,sizeof(f));///预处理成非法情况 
	dfs(1);
	write(f[1][mc]);
	printf("\n");
	return 0;//Over!!! 
} 
//in:
//10 2
//1 8 2
//1 9 2
//1 10 1
//1 3 2
//1 4 2
//1 7 2
//8 5 3
//10 2 1
//10 6 2
//ans:135; 
////自己建的特殊数据，供检查，也可以通过模拟可以更直观了解预处理f数组的作用