/ SeriousOJ /

Record Detail

Accepted


  
# Status Time Cost Memory Cost
#1 Accepted 2ms 788.0 KiB
#2 Accepted 2ms 836.0 KiB
#3 Accepted 45ms 2.453 MiB
#4 Accepted 2ms 908.0 KiB
#5 Accepted 2ms 788.0 KiB

Code

#include <bits/stdc++.h>

#pragma GCC optimize("Ofast")
using namespace std;

void solve() {
  int n, q;
  cin >> n >> q;
  vector<vector<int>> g(n);

  for (int i = 0; i < n - 1; i++) {
    int u, v;
    cin >> u >> v;
    --u, --v;
    g[u].push_back(v);
    g[v].push_back(u);
  }

  vector<int> dist(n, -1);
  queue<int> Q;

  dist[0] = 0;
  Q.push(0);

  while (!Q.empty()) {
    int node = Q.front();
    Q.pop();

    for (int neighbor : g[node]) {
      if (dist[neighbor] == -1) {
        dist[neighbor] = dist[node] + 1;
        Q.push(neighbor);
      }
    }
  }

  int lim = 1e5 + 2;
  vector<int> ans(lim, 0);

  for (int i = 0; i < n; i++) {
    if (dist[i] < lim) {
      ans[dist[i]]++;
    }
  }

  for (int i = 1; i < lim; i++) {
    ans[i] += ans[i - 1];
  }

  while (q--) {
    int x;
    cin >> x;
    if (x < lim) {
      cout << ans[x] << "\n";
    } else {
      cout << n << "\n";
    }
  }
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int tc = 1;
  cin >> tc;
  for (int cs = 1; cs <= tc; cs++) {
    solve();
  }
  return 0;
}

Information

Submit By
Type
Submission
Problem
P1053 Water on Tree
Language
C++20 (G++ 13.2.0)
Submit At
2024-07-11 03:58:06
Judged At
2024-11-11 03:27:45
Judged By
Score
100
Total Time
45ms
Peak Memory
2.453 MiB