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

输入 #1

6 5
2 3
3 4
3 5
5 6
2 6
7
1 1
2 2
2 0
2 3
4 1
6 0
4 3

输出 #1

1
20
2
20
7
6
20

说明/提示

限制条件

• $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 翻译