Description Input 多组用例，每组用例首先输入两整数n和k，之后n-1行每行三个整数u,v,w表示u和v之间有一条边权为w的树边，以文件尾结束输入(1<=k<=n<=1e6,1<=w<=1e5) Output 输出res最大值 Sample Input 5 4 1 2 3 2 3 4 2 4 5 2 5 6 Sample Output 27 Solution 以1为根dfs整棵树，对于一条树边u->v，设其边权为w，其对答案的贡献为以v为根的子树中的1点属于不同集合的个数，由于至多k个集合，所以该条边的贡献至多为w*min(k,Size(v))，Size(v)是以v为根的子树中节点个数，通过构造可以使得每一条边都做出最大贡献，所以一遍dfs求出所有Size即可得到每条边的贡献，累加起来即为答案 Code
#include<cstdio> #include<iostream> #include<cstring> #include<algorithm> #include<cmath> #include<vector> #include<queue> #include<map> #include<set> #include<ctime> using namespace std; typedef long long ll; typedef pair<int,int>P; const int maxn=1000001; vector<P>g[maxn]; int T,n,k,Size[maxn]; ll ans=0; void dfs(int u,int fa) { Size[u]=1; for(int i=0;i<g[u].size();i++) { int v=g[u][i].first,w=g[u][i].second; if(v==fa)continue; dfs(v,u); ans+=(ll)min(k,Size[v])*w; Size[u]+=Size[v]; } } int main() { while(~scanf("%d%d",&n,&k)) { for(int i=1;i<=n;i++)g[i].clear(); for(int i=1;i<n;i++) { int u,v,w; scanf("%d%d%d",&u,&v,&w); g[u].push_back(P(v,w)),g[v].push_back(P(u,w)); } ans=0; dfs(1,0); printf("%I64d\n",ans); } }