关于 wqs 二分的答案输出

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 并碰巧数据水然后过了吗？