/ SeriousOJ /

Record Detail

Accepted


  
# Status Time Cost Memory Cost
#1 Accepted 4ms 580.0 KiB
#2 Accepted 4ms 576.0 KiB
#3 Accepted 37ms 3.496 MiB
#4 Accepted 4ms 360.0 KiB
#5 Accepted 4ms 576.0 KiB

Code

#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long int ll;

const int MAX = 2e5 + 7, MOD = 1e9 + 7;

std::vector<int> g[MAX];

ll prefixSum[MAX];

int maximumDepth, numberOfNodes[MAX];

void dfs(int u, int p, int depth) {
  ll sum = 0;
  for (auto v : g[u]) {
    if (p != v) {
      dfs(v, u, depth + 1);
    }
  }
  maximumDepth = max(maximumDepth, depth);
  numberOfNodes[depth]++;
}
void clear(int n) {
  for (int i = 0; i <= n; i++) {
    g[i].clear();
    prefixSum[i] = 0;
    numberOfNodes[i] = 0;
  }
  maximumDepth = 0;
}
void solve() {
  int n, q; cin >> n >> q;
  for (int i = 1; i < n; i++) {
    int u, v; cin >> u >> v;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  dfs(1, 1, 0);
  prefixSum[0] = 1;
  for (int i = 1; i <= maximumDepth; i++) {
    prefixSum[i] = prefixSum[i - 1] + numberOfNodes[i];
  }
  while (q--) {
    int x;
    cin >> x;
    if (x > maximumDepth)x = maximumDepth;
    cout << prefixSum[x] << endl;
  }
  clear(n);
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);

  int t = 1;
  cin >> t;
  for (int tc = 1; tc <= t; tc++) {
    //cout<<"case "<<tc<<": ";
    solve();
  }
  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:38:07
Judged At
2024-10-03 13:49:54
Judged By
Score
100
Total Time
37ms
Peak Memory
3.496 MiB