/ SeriousOJ /

Record Detail

Accepted


  
# Status Time Cost Memory Cost
#1 Accepted 1ms 540.0 KiB
#2 Accepted 1ms 540.0 KiB
#3 Accepted 169ms 2.309 MiB
#4 Accepted 1ms 540.0 KiB
#5 Accepted 1ms 552.0 KiB

Code

#include<bits/stdc++.h>

//#include <Windows.h> Sleep(300);
using namespace std;
//#define int long long
#define endl '\n'
#define vi vector<int>
#define pii pair<int, int>
#define pb push_back
#define mod 1000000007
#define log(args...){ string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); cout<<endl; }

void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
	cout << *it << " = " << a << " ";
	err(++it, args...);
}
#define fr(i, n) for(int i=0; i<n; i++)
#define fr1(i, n) for(int i=1; i<=n; i++)
#define fab(i, a, b) for(int i=a; i<b; i++)
const int dx[]={+1,-1,+0,+0};
const int dy[]={+0,+0,+1,-1};


void dfs(vector<vi>& g, vi& vis, int node, vi& level, int step){
    vis[node] = 1;
    level[node] = step;
    for(auto child: g[node]) if(not vis[child]) dfs(g, vis, child, level, step+1);
}
void bfs(vector<vi>& g, vi& vis, int node, vi& level){
    vis[node] = 1;
    queue<int> q;
    q.push(node);
    level[node] = 0;

    while(not q.empty()){
        int top = q.front(); q.pop();
        for(auto child: g[top]){
            if(not vis[child]){
                vis[child] = 1;
                q.push(child);
                level[child] = level[top] + 1; // **level[top]
            }
        }
    }
}
int32_t main() {
    int t=1; cin>>t;
    while(t--){
        int n, q; cin>>n>>q;
        vector<vi> g(n+1);
        for(int i=1; i<n; i++) {
            int u, v; cin>>u>>v;
            g[u].pb(v);
            g[v].pb(u);
        }
        //cout<<"DONE"<<endl;
        vector<int> vis(n+1, 0), level(n+1, 0) ;
        bfs(g, vis, 1, level);
        //fr(i, n+1) log(i, level[i]);

        int freq[n+1]={0};
        for(auto x: level) freq[x]++;
        //fr(i, n+1) log(i, freq[i]);
        freq[0] = 1; // 0 number second e 1ta vore ase
        for(int i=1; i<=n; i++) freq[i] += freq[i-1]; // 1 number second e age joto vora chilo toto jog hobe 1 number second e jotogula vora chilo tar sathe
        //fr1(i, n) log(i, freq[i]);
        while(q--){
            int x; cin>>x;
            cout<<freq[x]<<endl;
        }
   }

}

Information

Submit By
Type
Submission
Problem
P1053 Water on Tree
Language
C++20 (G++ 13.2.0)
Submit At
2024-05-07 19:14:53
Judged At
2024-05-07 19:14:53
Judged By
Score
100
Total Time
169ms
Peak Memory
2.309 MiB