wqs 的疑惑

手造小数据没问题，交上全挂。

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define deb(var) cerr << #var << '=' << (var) << "; "
#define int long long
int n, k;
vector<pii> g[300010];
int mid;
struct Pair {
	int x, y;
	Pair() {}
	Pair(int a, int b) {
		x = a, y = b;
	}
	bool operator < (Pair b) const { return x == b.x ? y < b.y : x < b.x; }
	friend Pair operator + (Pair a, int b) {
		return Pair(a.x + b, a.y);
	}
	friend Pair operator + (int b, Pair a) {
		return a + b;
	}
	friend Pair operator + (Pair a, Pair b) {
		return Pair(a.x + b.x, a.y + b.y);
	}
};
Pair f[300010][5];
void dp(int u, int fa) {
	f[u][2] = Pair(mid, 1);
	f[u][0] = Pair(0, 0); f[u][1] = Pair(-1e18, 0);
	for (int i = 0; i < g[u].size(); i++) {
		int v = g[u][i].fi, w = g[u][i].se;
		if (v == fa) continue;
		dp(v, u);
		Pair f0 = f[u][0], f1 = f[u][1], f2 = f[u][2];
		for (int j = 0; j <= 2; j++) f[u][j] = max(f[u][j], f[u][j] + max(f[v][0], max(f[v][1], f[v][2])));
		f[u][1] = max(f[u][1], f0 + w + f[v][1]);
		f1.y--;
		f[u][2] = max(f[u][2], f1 + w + f[v][1]);
	}
	f[u][1] = max(f[u][1], f[u][0] + Pair(mid, 1)); 
}
signed main() {
	cin >> n >> k; k++; 
	for (int i = 1; i < n; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		g[u].pb(mp(v, w)); g[v].pb(mp(u, w));
	}
	int l = -1e12, r = 1e12, xx = 0;
	while (l < r) {
		mid = (l + r + 1) >> 1;
		dp(1, 0);
		int x = max(f[1][0], max(f[1][1], f[1][2])).x, y = max(f[1][0], max(f[1][1], f[1][2])).y;
//		deb(mid), deb(x), deb(y)<<"\n";
		if (y <= k) l = mid, xx = x - mid * k; else r = mid - 1; 
	} 
	cout << xx << "\n";
	return 0;
}
/*
Hack:
5 1
1 2 3
2 3 -5
2 4 -3
4 5 6
*/