E - Small d and k

题目描述：

  给\(n\)个顶点\(m\)条边的无向图，每个顶点的度不超过\(3\)，给你\(Q\)次询问，每次询问给你一个顶点\(x\)和一个\(k\)，表示求距离顶点\(x\)的长度不超过\(k\)的顶点标号之和。

思路:

  关键在每一个点的度是不超过\(3\)的，所以可以考虑对每一个询问的点做一遍\(BFS\),每一次搜索的点不会超过\(3 * 3 * 3\)个点，所以查询的复杂度不会超过\(O(30q)\)。在\(BFS\)的时候不能光存一个当前的节点编号\(i\)，还需要存一个变量\(d\)，表示从初始点到当前点的距离，如果大于\(k\)就不继续搜下去.

    auto bfs = [&](int u, int k) -> int {
        std::queue<std::array<int, 2>> q;
        q.push({u, 0});
        std::vector<bool> vis(n + 1);

        int ans = 0;
        while(q.size()) {
            std::array<int, 2> t = q.front();
            q.pop();
            if (vis[t[0]] || t[1] > k) continue;
            ans += t[0];
            vis[t[0]] = true;
            for (auto& v : adj[t[0]]) {
                q.push({v, t[1] + 1});
            }
        }
        return ans;
    };