真是哭了，今天多校的图论题，算得上是在比赛的时候的进阶题目，A了这道就能挤开一大片那种……
没A，思路错了……
题意：
给你一棵树，要你将 { 2，3，4……n } 进行划分成 k 个集合，每个集合与{ 1 }相并后 求 最小 斯坦纳树，求和的最大值。
思路：
考虑每条边贡献值，只可能是 k 与 子树结点的最小值，将贡献值与边长相乘累加后便是答案。原因yy即可。
一边dfs得出每个结点的子树结点数，复杂度 O ( n ) 。
AC Code
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 5;
int head[maxn];
int pre[maxn], num[maxn];
ll ans;
int n, idx, m;
struct node {
int to, weight, next;
} edges[maxn << 1];
void addEdge(int u, int v, int w)
{
edges[idx].to = v;
edges[idx].weight = w;
edges[idx].next = head[u];
head[u] = idx++;
}
void init()
{
for (int i = 0; i <= n; i++)
head[i] = -1;
idx = ans = 0;
}
int dfs(int u, int p)
{
num[u] = 1;
for (int id = head[u]; ~id; id = edges[id].next)
if (edges[id].to != p) {
pre[edges[id].to] = edges[id].weight;
num[u] += dfs(edges[id].to, u);
}
ans += min(num[u], m) * 1LL * pre[u];
return num[u];
}
int main()
{
int u, v, w;
while (scanf("%d %d", &n, &m) != EOF) {
init();
for (int i = 1; i < n; i++) {
scanf("%d %d %d", &u, &v, &w);
addEdge(u, v, w);
addEdge(v, u, w);
}
dfs(1, 0);
printf("%lld\n", ans);
}
return 0;
}