题解 | E. 代号 N

E. 代号 N

笔者出的题，我们设第 条分支对应分配了 个脉冲设备

只需要在 的前提下，使得 最小即可

这个问题结构本身就是一个经典的二分答案，假设 的上界后看看所需要的 够不够即可

也可以贪心+指针去做，在 排序并前缀和预处理后，两者都可以高效解决

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

#define fType int
#define foreach(x, a, b) for (fType x = a, _end_ = b; x <= _end_; x++)
#define foreach_sub(x, a, b) for (fType x = a, _end_ = b; x >= _end_; x--)
#define tpl make_tuple

int main()
{
    ios::sync_with_stdio(0), cin.tie(0);

    int n, k;
    cin >> n >> k;

    using pr = pair<ll, int>;
    vector<vector<pr>> gp(n + 1);
    foreach (i, 1, n - 1)
    {
        int u, v;
        ll w;
        cin >> u >> v >> w;

        gp[u].emplace_back(w, v);
        gp[v].emplace_back(w, u);
    }

    int rt = 0;
    foreach (i, 1, n)
    {
        if (gp[i].size() == 3)
        {
            rt = i;
            break;
        }
    }

    array<vector<ll>, 3> ls{};
    vector<ll> tmp;
    tmp.reserve(n);

    int tot = 0;
    auto dfs = [&](auto &self, int u, int fa) -> void
    {
        if (gp[u].size() == 1)
        {
            ls[tot] = vector(tmp.begin(), tmp.end());
            sort(ls[tot].begin(), ls[tot].end());

            tmp.clear();
            ++tot;

            return;
        }

        for (auto [w, v] : gp[u])
        {
            if (v == fa) continue;

            tmp.emplace_back(w);
            self(self, v, u);
        }
    };
    dfs(dfs, rt, 0);

    ll L = 0, R = -1, mid, myans = -1;
    foreach (t, 0, 2)
    {
        int sz = ls[t].size();
        foreach (i, 1, sz - 1)
            ls[t][i] += ls[t][i - 1];

        R = max(R, ls[t][sz - 1]);
    }

    auto chk = [&](ll mid) -> bool
    {
        int cnt = 0;
        foreach (t, 0, 2)
            cnt += distance(upper_bound(ls[t].begin(), ls[t].end(), mid), ls[t].end());

        return cnt <= k;
    };

    while (L <= R)
    {
        mid = L + (R - L) / 2;

        if (chk(mid))
            myans = mid, R = mid - 1;
        else
            L = mid + 1;
    }
    cout << myans << "\n";

    return 0;
}

扩展思考：如果第 条边的所需的脉冲设备不再是固定的 ，而是 ，怎么做呢？