/ SeriousOJ /

Record Detail

Accepted


  
# Status Time Cost Memory Cost
#1 Accepted 5ms 4.383 MiB
#2 Accepted 5ms 4.312 MiB
#3 Accepted 41ms 7.902 MiB
#4 Accepted 5ms 4.281 MiB
#5 Accepted 5ms 4.211 MiB

Code

#include<bits/stdc++.h>
using namespace std;

#define ll unsigned long long
#define endl '\n'

const int N = 1e5+12;
std::vector<int>gp[N];

ll lv[N];
bool vis[N];
void bfs(int sr){
    
    std::queue<int>s;
    s.push(sr);
    vis[sr] = 1;
    lv[sr] = 0;
    
    while(!s.empty()){
        int node = s.front();
        s.pop();
        
        for(auto u : gp[node]){
            if(!vis[u]){
                vis[u] = 1;
                s.push(u);
                lv[u] = lv[node]+1;
            }
        }
    }
}

void solve(int cs){
    int n,q;
    cin>>n>>q;
    memset(gp,0,sizeof gp);
    memset(lv,0,sizeof lv);
    memset(vis,0,sizeof vis);
    for(int i = 1; i < n; i++){
        int a,b;cin>>a>>b;
        gp[a].push_back(b);
        gp[b].push_back(a);
    }
    bfs(1);
    vector<ll>v(N,0);
    for(int i = 1; i <= n; i++){
        v[lv[i]]++;
    }
    for(int i = 1; i < N; i++)v[i]+=v[i-1];
    
    while(q--){
        int x;
        cin>>x;
        cout<<v[x]<<endl;
    }
}
   
int main()
{

    ios_base::sync_with_stdio(false);cin.tie(0);
    int t=1,cs=0;
    cin >> t;
    while(t--)
    {
        solve(++cs);
    }

    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:04:12
Judged At
2024-10-03 13:50:50
Judged By
Score
100
Total Time
41ms
Peak Memory
7.902 MiB