RT.

目前只从惩罚角度感性理解 wqs 二分，对于最后答案的输出有个问题，我记得最后输出的答案应该是二分到的答案 $\times$ 题目限制的 $k + 1$ 个联通块，但是这样会 $85$ 分，代码如下：

#include <cstdio>
#include <vector>
#include <utility>

#define fst first
#define sec second

typedef long long LL;
typedef std::pair<int, int> pii;

const int MAXN = 3e5 + 5;
const LL INF = 0x3f3f3f3f3f3f3f3f;

int n, m;

struct Str {
	LL val; int cnt;
	Str operator+ (const Str& A) const {
		Str res;
		res.val = val + A.val, res.cnt = cnt + A.cnt;
		return res;
	}
} f[MAXN << 1][3];

std::vector<pii> G[MAXN << 1];

LL ext;

Str MAX(Str A, const Str B) {
	if (A.val == B.val) return A.cnt > B.cnt ? A : B;
	return A.val > B.val ? A : B;
}

void dfs(int u, int father) {
	for (auto x : G[u]) {
		int k = x.fst, val = x.sec;
		if (k != father) {
			dfs(k, u);
			f[u][2] = MAX(f[u][2] + f[k][0], f[u][1] + f[k][1] + (Str){ val - ext, -1 });
			f[u][1] = MAX(f[u][1] + f[k][0], f[u][0] + f[k][1] + (Str){ val, 0 });
			f[u][0] = f[u][0] + f[k][0];
		}
	}
	f[u][0] = MAX(MAX(f[u][0], f[u][1]), f[u][2]);
}

void solve(LL mid) {
	ext = mid;
	for (int i = 1; i <= n; ++i) {
		f[i][0] = (Str){ 0LL, 0 };
		f[i][1] = (Str){ ext, 1 };
		f[i][2] = (Str){ -INF, 0 };
	}
	dfs(1, 0);
}

int main() {

	scanf("%d %d", &n, &m); ++m;
	for (int i = 1; i < n; ++i) {
		int x, y, val;
		scanf("%d %d %d", &x, &y, &val);
		G[x].emplace_back(y, val), G[y].emplace_back(x, val);
	}
	LL l = -1e12, r = 1e12, res;
	while (l <= r) {
		LL mid = l + r >> 1;
		solve(mid);
		if (f[1][0].cnt <= m) res = mid, l = mid + 1;
		else r = mid - 1;
	}
	solve(res);
	printf("%lld\n", f[1][0].val - res * m);

	return 0;
}

发现之前的讨论帖也有人有这个问题：link

按照下面人的回答更改了代码并通过了此题，但是似乎与 wqs 二分的正确的答案输出相反，而且题解都是按照我理解的正确的输出方式输出的。

是代码有 bug 并碰巧数据水然后过了吗？