这题是一个DP
每次考虑两棵子树的贡献，然后把两棵子树合并起来，中间的转移类似树上背包
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=2005;
int n,K,en,h[N],siz[N],vis[N];
long long dp[N][N],tp[N];
struct Edge{
int b,next;
long long v;
}e[N<<1];
void AddEdge(int sa,int sb,long long sc){
e[++en].b=sb;
e[en].v=sc;
e[en].next=h[sa];
h[sa]=en;
}
void DP(int u){
siz[u]=vis[u]=1;
for(int i=h[u];i;i=e[i].next){
int v=e[i].b;
if(vis[v])continue;
DP(v);
for(int j=0;j<=K;j++)tp[j]=dp[u][j];
for(int j=0;j<=min(siz[u],K);j++){
for(int k=0;k<=min(siz[v],K);k++){
tp[j+k]=max(tp[j+k],dp[v][k]+dp[u][j]+e[i].v*(k*(K-k)+(siz[v]-k)*(n-K-(siz[v]-k))));
}
}
siz[u]+=siz[v];
for(int j=0;j<=siz[u];j++)dp[u][j]=max(dp[u][j],tp[j]);
}
}
int main(){
freopen("4033.in","r",stdin);
freopen("4033.out","w",stdout);
scanf("%d %d",&n,&K);
for(int i=1;i<n;i++){
int u,v,w;
scanf("%d %d %d",&u,&v,&w);
AddEdge(u,v,w);AddEdge(v,u,w);
}
DP(1);
printf("%lld\n",dp[1][K]);
return 0;
}
评论 (0)
