\(\text{Solution:}\)
考虑对于一个点,从它子树再中选择 \(k\) 个黑点的代价:\(e[i].dis \cdot (p-k)*k+(siz[j]-k)*(n-p-siz[j]+k).\)
于是状态转移方程就写好了:
\(dp[x][T]=dp[x][T]=Max(dp[x][T],dp[x][T-k]+dp[j][k]+v*(k*(p-k)+(siz[j]-k)*(n-p-siz[j]+k)))\)
同时注意要记得把子树中全是白点的情况记录一下:
\(dp[x][T]+=dp[j][0]+siz[j]*(n-p-siz[j])*v\)
#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef long long ll;
const int MAXN=3001;
const ll dyx=(1LL<<60);
inline ll read(){
ll s=0,w=1;
char ch=getchar();
while(!isdigit(ch)){
if(ch==‘-‘)w=-1;
ch=getchar();
}
while(isdigit(ch)){
s=s*10-48+ch;
ch=getchar();
}
return s*w;
}
int n,p,siz[MAXN];
ll dp[MAXN][MAXN];
int head[MAXN],tot;
struct E{int nxt,to,dis;}e[MAXN<<1];
inline int Max(int x,int y){return x>y?x:y;}
inline int Min(int x,int y){return x<y?x:y;}
inline void add(int x,int y,int w){
e[++tot]=(E){head[x],y,w};
head[x]=tot;
}
void dfs(int x,int fa){
siz[x]=1;dp[x][0]=dp[x][1]=0;
for(int i=head[x];i;i=e[i].nxt){
int j=e[i].to;
if(j==fa)continue;
dfs(j,x);
int v=e[i].dis;siz[x]+=siz[j];
for(int T=Min(siz[x],p);T>=0;--T){
if(dp[x][T]!=-1){
dp[x][T]+=dp[j][0]+siz[j]*(n-p-siz[j])*v;
}
for(int k=Min(T,siz[j]);k;--k){
if(dp[x][T-k]==-1)continue;
dp[x][T]=Max(dp[x][T],dp[x][T-k]+dp[j][k]+v*(k*(p-k)+(siz[j]-k)*(n-p-siz[j]+k)));
}
}
}
}
signed main(){
// freopen("111.txt","r",stdin);
n=read(),p=read();
if(n-p<p)p=n-p;
for(int i=1;i<n;++i){
int x=read(),y=read(),v=read();
// read(x);read(y);read(v);
add(x,y,v);add(y,x,v);
}
memset(dp,-1,sizeof dp);
dfs(1,0);
ll ans=dp[1][p];
printf("%lld\n",ans);
return 0;
}