/ SeriousOJ /

Record Detail

Accepted


  
# Status Time Cost Memory Cost
#1 Accepted 1ms 532.0 KiB
#2 Accepted 2ms 532.0 KiB
#3 Accepted 40ms 2.289 MiB
#4 Accepted 1ms 320.0 KiB
#5 Accepted 1ms 324.0 KiB

Code


#include <bits/stdc++.h>

#ifdef LOCAL
#include "../algo/debug.h"
#else 
#define debug(...) 0
#endif

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int tt;
  cin >> tt;
  while (tt--) {
    int n, q;
    cin >> n >> q;
    vector<vector<int>> e(n);
    for (int i = 0; i < n - 1; i++) {
      int u, v;
      cin >> u >> v;
      u--;
      v--;
      e[u].push_back(v);
      e[v].push_back(u);
    }
    vector<int> que(1), d(n, -1), f(n);
    d[0] = 0;
    f[0] = 1;
    for (int i = 0; i < (int) que.size(); i++) {
      int v = que[i];
      for (int u : e[v]) {
        if (d[u] == -1) {
          f[d[u] = d[v] + 1] += 1;
          que.push_back(u);
        }
      }
    }
    assert((int) que.size() == n);
    for (int i = 1; i < n; i++) {
      f[i] += f[i - 1];
    }
    while (q--) {
      int x;
      cin >> x;
      cout << f[min(x, n - 1)] << '\n';
    }
  }
  return 0;
}

Information

Submit By
Type
Submission
Problem
P1053 Water on Tree
Contest
Brain Booster #3
Language
C++20 (G++ 13.2.0)
Submit At
2024-05-06 16:19:32
Judged At
2024-10-03 13:50:32
Judged By
Score
100
Total Time
40ms
Peak Memory
2.289 MiB