传送门
题意：
给了一棵以1为原点，n个点的树，然后将其余的n-1个点分成k个部分，每个部分又都是以1为根的最小斯坦纳树，求k个最小斯坦纳树的边权最大总值。
思路：
1、由于是在一棵树上选边，所以其实不存在建最小斯坦纳树的问题；
2、贪心的思想，对于每一条边，方向为从父节点到子节点，其所能达到的最大贡献为，len * Max（k,son_node），其中 len 为边的长度，sum_node为子节点及其子树的总点数。每一条边的最大值即为全部的最大值。
#include <bits/stdc++.h> using namespace std; #define N 1000005 #define LL long long int tot; struct edge { int v,nxt,len; }e[N<<1]; int head[N]; void add(int a,int b,int c) { e[tot].v = b; e[tot].nxt = head[a]; e[tot].len = c; head[a] = tot++; } LL ans; int k; int dfs(int p,int pre) { int num = 0; for(int i=head[p];~i;i=e[i].nxt){ int v = e[i].v; if(v == pre) continue; int cot = dfs(v,p); ans += (LL)e[i].len * min(k,cot); num += cot; } return num + 1; } int main() { int n; while(~scanf("%d%d",&n,&k)){ memset(head,-1,sizeof(head)); tot = 0; for(int i=1;i<n;i++){ int a,b,c; scanf("%d%d%d",&a,&b,&c); add(a,b,c); add(b,a,c); } ans = 0; dfs(1,-1); printf("%lld\n",ans); } }
