/ SeriousOJ /

Record Detail

Accepted


  
# Status Time Cost Memory Cost
#1 Accepted 1ms 540.0 KiB
#2 Accepted 1ms 540.0 KiB
#3 Accepted 43ms 2.938 MiB
#4 Accepted 1ms 540.0 KiB
#5 Accepted 1ms 488.0 KiB

Code

#include <bits/stdc++.h>

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

void solve(int cs) {
  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> d(n, -1);
  d[0] = 0;
  auto dfs = [&](auto &&self, int node, int par) -> void {
    for (auto &nodes : g[node]) {
      if (nodes != par) {
        if (d[nodes] == -1) d[nodes] = d[node] + 1;
        self(self, nodes, node);
      }
    }
  };
  
  dfs(dfs, 0, -1);
  vector<int> res (2 * n, 0);
  for (int i = 0; i < n; i++) {
    res[d[i]] += 1;
  }
  for (int i = 1; i < 2 * n; i++) res[i] += res[i - 1];

  while (q--) {
    int v;
    cin >> v;
    if (v >= 2 * n) cout << n << "\n";
    else cout << res[v] << "\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(cs);
  }
  return 0;
}

Information

Submit By
Type
Submission
Problem
P1053 Water on Tree
Language
C++20 (G++ 13.2.0)
Submit At
2024-07-11 09:33:27
Judged At
2024-07-11 09:33:27
Judged By
Score
100
Total Time
43ms
Peak Memory
2.938 MiB