1 条题解
-
1
#include <bits/stdc++.h> #define ull unsigned long long #define ll long long using namespace std; const int N=2005; int n,m,k,s,t,size[N]; ll f[N][N],g[N]; vector<pair<int,ll>> e[N]; void dfs(int u,int fa){ f[u][0]=f[u][1]=0; size[u]=1; for (auto &o:e[u]){ int v=o.first; if (v==fa) continue; dfs(v,u); for (int i=size[u];i>=0;--i) for (int j=size[v];j>=0;--j)//因为j会取到0,所以j也需要倒序枚举 f[u][i+j]=max(f[u][i+j],f[u][i]+f[v][j]+o.second*(j*(m-j)+(size[v]-j)*(n-m-size[v]+j))); size[u]+=size[v]; } } int main() { ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); cin>>n>>m; for (int i=1;i<n;++i){ cin>>s>>t>>k; e[s].push_back({t,k}); e[t].push_back({s,k}); } dfs(1,0); cout<<f[1][m]; }
- 1
信息
- ID
- 370
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- 3
- 标签
- 递交数
- 36
- 已通过
- 23
- 上传者