AT_abc254_e [ABC254E] Small d and k

有一个包含 $N$ 个顶点、$M$ 条边的简单无向图，每个顶点编号为 $1,\ldots,N$。对于 $i=1,\ldots,M$，第 $i$ 条边连接顶点 $a_i$ 和顶点 $b_i$。此外，**每个顶点的度数不超过 $3$。** 对于 $i=1,\ldots,Q$，请回答以下查询： - 求与顶点 $x_i$ 的距离不超过 $k_i$ 的所有顶点编号之和。

输入以如下格式从标准输入读入。 > $N$ $M$ > $a_1$ $b_1$ > $\vdots$ > $a_M$ $b_M$ > $Q$ > $x_1$ $k_1$ > $\vdots$ > $x_Q$ $k_Q$

输出 $Q$ 行。第 $i$ 行输出第 $i$ 个查询的答案。

## 限制条件 - $1 \leq N \leq 1.5 \times 10^5$ - $0 \leq M \leq \min\left(\frac{N(N-1)}{2}, \frac{3N}{2}\right)$ - $1 \leq a_i < b_i \leq N$ - 若 $i \neq j$，则 $(a_i, b_i) \neq (a_j, b_j)$ - 给定图中每个顶点的度数不超过 $3$ - $1 \leq Q \leq 1.5 \times 10^5$ - $1 \leq x_i \leq N$ - $0 \leq k_i \leq 3$ - 所有输入均为整数 ## 样例解释 1 对于第 $1$ 个查询，与顶点 $1$ 的距离不超过 $1$ 的顶点只有顶点 $1$，因此答案为 $1$。对于第 $2$ 个查询，与顶点 $2$ 的距离不超过 $2$ 的顶点为顶点 $2,3,4,5,6$，这些编号的总和为 $20$，因此答案为 $20$。第 $3$ 个及以后的查询同理可以得到答案。 由 ChatGPT 4.1 翻译