题意：问你把点分成k个集合，最大生成树是大多。
当时比赛的时候想了好久，都没想出来，后面一看，哇，是我们太傻了
思路：把他分成k个集合的点，怎么最大，其实是边经过最多才是最大，就尽量让k的集合更分散。
我们知道这个节点的size，我们经过这个节点的边的次数是min（siz，k）这个其实很好理解对吧。
所以依次，我们就能解得答案。
/* gyt Live up to every day */ #include<cstdio> #include<cmath> #include<iostream> #include<algorithm> #include<vector> #include<stack> #include<cstring> #include<queue> #include<set> #include<string> #include<map> #include <time.h> #define PI acos(-1) using namespace std; typedef long long ll; typedef double db; const int maxn = 2e6+10; const ll maxm = 1e7; const int modd = 10000007; const int INF = 1<<30; const db eps = 1e-9; struct Edge{ int v, next, w; }edge[maxn]; int head[maxn], cnt; int siz[maxn], pre[maxn]; void init() { memset(head, -1, sizeof(head)); cnt=0; memset(siz, 0, sizeof(siz)); memset(pre, 0, sizeof(pre)); } void add(int u, int v, int w) { edge[cnt].v=v, edge[cnt].w=w; edge[cnt].next=head[u]; head[u]=cnt++; } void dfs(int u, int fa) { siz[u]=1; for (int i=head[u]; ~i; i=edge[i].next) { int v=edge[i].v; if (v!=fa) { pre[v]=edge[i].w; dfs(v, u); siz[u]+=siz[v]; } } } void solve() { int n, k; while(scanf("%d%d", &n, &k)!=EOF) { init(); for (int i=0; i<n-1; i++) { int a, b, c; scanf("%d%d%d", &a, &b, &c); add(a, b, c); add(b, a, c); } dfs(1, -1); ll ans=0; for (int i=2; i<=n; i++) { ans += (ll)pre[i]*min(siz[i], k); } printf("%lld ", ans); } } int main() { int t = 1; //freopen("in.txt", "r", stdin); //scanf("%d", &t); //getchar(); while(t--) solve(); return 0; }