摘要
Title: 3712. 根能抵达的点
Tag: DFS、二分
Memory Limit: 64 MB
Time Limit: 1000 ms

3712. 根能抵达的点

题意

给定一棵由 N 个节点构成的带边权树。
节点编号从 0 到 N−1，其中 0 号点为根节点。
最初，从根节点可以抵达所有节点（包括自己）。
如果我们将所有边权小于 X 的边全部删掉，那么从根节点可以抵达的节点数目就可能发生改变。
现在，给定一个整数 Y，请你找到最小的非负整数 X，使得所有边权小于 X 的边都被删掉以后，根节点能够抵达的节点数目（包括自己）不超过 Y。
思路

二分X即可，X最大为最大的边+1
每次选X，都进行一次DFS，看看剩下多少点

代码

/*
* @Author: NEFU AB-IN
* @Date: 2022-08-17 11:01:52
* @FilePath: \Acwing\3712\3712.cpp
* @LastEditTime: 2022-08-17 15:06:25
*/
#include <bits/stdc++.h>
using namespace std;
#define N n + 100
#define int long long
#define SZ(X) ((int)(X).size())
#define IOS                                                                                                            \
    ios::sync_with_stdio(false);                                                                                       \
    cin.tie(nullptr);                                                                                                  \
    cout.tie(nullptr)
#define DEBUG(X) cout << #X << ": " << X << '\n'
typedef pair<int, int> PII;

void solve()
{
    int n, y, mx = 0;
    cin >> n >> y;

    vector<PII> g[N];
    for (int i = 1; i < n; ++i)
    {
        int u, v, w;
        cin >> u >> v >> w;
        g[u].push_back({v, w});
        g[v].push_back({u, w});
        mx = max(mx, w);
    }

    int cnt = 0;
    function<void(int, int, int)> dfs = [&](int u, int fa, int x) {
        cnt++;
        for (auto [v, w] : g[u])
        {
            if (v == fa)
                continue;
            if (w >= x)
                dfs(v, u, x);
        }
    };

    auto check = [&](int x) {
        dfs(0, -1, x);
        return cnt <= y;
    };

    int l = 0, r = mx + 1;
    while (l < r)
    {
        cnt = 0;
        int mid = l + r >> 1;
        if (check(mid))
            r = mid;
        else
            l = mid + 1;
    }

    cout << l << '\n';

    return;
}

signed main()
{
    IOS;
    int T;
    cin >> T;
    while (T--)
        solve();
    return 0;
}

3712. 根能抵达的点

题意

思路

代码