树形dp
f[i][j]表示以i为根时它的子树中有j个点为黑点的最大收益，那么将根从x变为y时，产生的贡献就是 (x及其子树中的黑点数*y及其子树中的黑点数+x及其子树中的白点数*y及其子树中的白点数)*边权v
记得开longlong
#include<cstdio> #include<cstring> #include<algorithm> #define LL long long #define N 2005 using namespace std; int read() { int a=0,f=1;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){a=a*10+c-'0';c=getchar();} return a*f; } struct edge{int next,to,v;}e[N*2]; int n,k,cnt; int son[N],head[N]; LL f[N],dp[N][N]; void add(int x,int y,int v) { e[cnt].next=head[x],e[cnt].to=y,e[cnt].v=v; head[x]=cnt++; } void solve(int x,int fa) { son[x]=1; for (int p=head[x];p!=-1;p=e[p].next) { int y=e[p].to; if (y==fa) continue; solve(y,x); for (int i=0;i<=k;i++) f[i]=0; int mx=min(k,son[x]),my=min(k,son[y]); for (int i=0;i<=mx;++i) for (int j=0;j<=min(k-i,my);++j) //因为y还没被计入x，是两棵独立的子树，所以可以这样枚举 f[i+j]=max(f[i+j],dp[x][i]+dp[y][j]+1ll*(j*(k-j)+(son[y]-j)*(n-k-(son[y]-j)))*e[p].v); //(两头黑点数乘积+两头白点数乘积)*边权v for (int i=0;i<=k;i++) dp[x][i]=f[i]; son[x]+=son[y]; } } int main() { n=read(),k=read(); memset(head,-1,sizeof(head)); memset(dp,0,sizeof(dp)); for(int i=1;i<n;++i) { int x=read(),y=read(),v=read(); add(x,y,v),add(y,x,v); } solve(1,0); printf("%lld",dp[1][k]); return 0; }
