Powered by:NEFU AB-IN

Link

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 
  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;
  }
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25
  26
  27
  28
  29
  30
  31
  32
  33
  34
  35
  36
  37
  38
  39
  40
  41
  42
  43
  44
  45
  46
  47
  48
  49
  50
  51
  52
  53
  54
  55
  56
  57
  58
  59
  60
  61
  62
  63
  64
  65
  66
  67
  68
  69
  70
  71
  72
  73
  74
  75