/ SeriousOJ /

Record Detail

Accepted


  
# Status Time Cost Memory Cost
#1 Accepted 2ms 416.0 KiB
#2 Accepted 2ms 500.0 KiB
#3 Accepted 128ms 3.078 MiB
#4 Accepted 2ms 532.0 KiB
#5 Accepted 2ms 328.0 KiB

Code

#include <bits/stdc++.h>

#define endl '\n'
#define F first
#define S second
#define pb push_back

typedef long long ll;
typedef unsigned long long ull;

using namespace std;

template<typename T>
void scan(vector<T> &v) {for (T &x : v) cin >> x;}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

#ifdef LUCHADOR
    freopen("/home/joker/Documents/code/in", "r", stdin);
    freopen("/home/joker/Documents/code/out", "w", stdout);
#endif

    int t;
    cin >> t;

    while (t--) {
        int n, q, x;
        cin >> n >> q;

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

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

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

        map<int, int> level_nodes;
        int max_level = 0;

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

            level_nodes[level[u]]++;
            max_level = max(max_level, level[u]);

            for (int &v : g[u]) {
                if (level[v] == -1) {
                    level[v] = level[u] + 1;
                    Q.push(v);
                }
            }
        }
        
        for (int i = 1; i <= max_level; ++i) {
            level_nodes[i] += level_nodes[i - 1];
        }

        while (q--) {
            cin >> x;

            if (x >= max_level) {
                cout << n << endl;
            } else {
                cout << level_nodes[x] << endl;
            }
        }
    }

    return 0;
}

Information

Submit By
Type
Submission
Problem
P1053 Water on Tree
Contest
Brain Booster #3
Language
C++17 (G++ 13.2.0)
Submit At
2024-05-06 17:40:40
Judged At
2024-10-03 13:48:11
Judged By
Score
100
Total Time
128ms
Peak Memory
3.078 MiB