qwq

蒟蒻求助...蜜汁20puts```cpp #include<bits/stdc++.h> using namespace std; typedef long long ll; const ll maxn=2010; const ll INF=2147483647; inline ll read() { ll x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-')f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=(x<<3)+(x<<1)+ch-'0'; ch=getchar(); } return xf; } inline void write(ll x) { if(x<0) { putchar('-'); x=-x; } if(x>9) { write(x/10); } putchar(x%10+'0'); } struct node { ll to,val; }; node cur; vector e[maxn]; vector e1[maxn]; ll n,k,x,y,dis,c[maxn],root=0,size[maxn],dp[maxn][maxn]; bool vis[maxn]; void dfs(ll x) { vis[x]=1; for(int i=0;i<e[x].size();i++) { if(!vis[e[x][i].to]) { node icur=e[x][i]; e1[x].push_back(icur); dfs(e[x][i].to); size[x]+=size[e[x][i].to]; } } return ; } void work(ll x) { dp[x][1]=0; dp[x][0]=0; for(int i=0;i<e1[x].size();i++) { work(e1[x][i].to); node icur=e1[x][i]; for(int j=min(k,size[icur.to]);j>=0;j--) { for(int t=0;t<=j;t++) { dp[x][j]=max(dp[x][j],dp[x][j-t]+dp[icur.to][t]+t(k-t)icur.val+icur.val(size[icur.to]-t)*(n-k-size[icur.to]+t)); } } } return ; } int main() { cin>>n>>k; for(int i=1;i<n;i++) { cin>>x>>y>>dis; cur.to=y; cur.val=dis; e[x].push_back(cur); cur.to=x; e[y].push_back(cur); c[y]++; c[x]++; } for(int i=1;i<=n;i++) { if(c[i]==1&&!root) { root=i; } size[i]=1; } dfs(root); memset(vis,0,sizeof(vis)); memset(dp,-1,sizeof(dp)); work(root); cout<<dp[root][k]<<endl; return 0; }