Description
给你一棵\(n\)个结点的无向树，每条边上有一个花费值。设\(S\)是\(n\)个结点的一个子集，定义\(f(S)\)为用树上的边把S中的结点都连通的最小花费。把除\(1\)以外的\(n-1\)个结点划分为至多\(k\)个非空集合\(S_1\)，\(S_2\)，...，\(S_k\)，问\(\sum_{i=1}^{k}{f(\{1\}\cup S_i)}\)最小可以为多少。\(1 \leqslant n,k \leqslant 10^6\)。
Input
多组用例，每组用例第一行给出给出两个整数\(n\)和\(k\)，接下来的\(n-1\)行每行给出三个数\(a\)，\(b\)和\(c\)，表示结点\(a\)和\(b\)之间有一套花费为\(c\)的边。
Output
每组用例输出一个整数表示答案。
Sample Input
5 41 2 32 3 42 4 52 5 6
Sample Output
27
Solution
计算每条边对答案的贡献。把\(1\)结点作为树根使其称为一棵有向树，对于每一条边\((u,v)\)，其中\(u\)是\(v\)的父节点，令\(num[v]\)表示以\(v\)为根的子树中的结点数量（包括\(v\)）,那么这条边最多可以被计算\(min\{k,num[v]\}\)次。可以找到一种划分方案， 使得每条边的贡献都达到最大。此时累加每条边的最大贡献就是最终答案。\(num[v]\)可在一遍dfs中得到。
Code
#include#include #include using namespace std;typedef long long ll;const int INF = 0x3f3f3f3f;const int N = 1e6 + 10;const int M = 2e6 + 10;struct Edge{ int to, w, next; Edge() {} Edge(int to, int w, int next): to(to), w(w), next(next) {}} edge[M];int adj[N], no;void init(){ memset(adj, -1, sizeof(adj)); no = 0;}void add(int u, int v, int w){ edge[no] = Edge(v, w, adj[u]); adj[u] = no++;}int num[N], fcost[N];int dfs(int u, int f){ num[u] = 1; for (int i = adj[u]; i != -1; i = edge[i].next) { int v = edge[i].to; if (v == f) { fcost[u] = edge[i].w; continue; } num[u] += dfs(v, u); } return num[u];}int main(){ int n, k; while (~scanf("%d%d", &n, &k)) { init(); for (int i = 1; i < n; i++) { int u, v, w; scanf("%d%d%d", &u, &v, &w); add(u, v, w); add(v, u, w); } dfs(1, 1); ll ans = 0; for (int i = 2; i <= n; i++) ans += (ll)fcost[i] * min(k, num[i]); printf("%lld\n", ans); } return 0;}