w 的 q 疑 s 惑

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
*/