分数: 500 点
问题陈述
我们有一个简单的无向图 N 顶点和 M 边缘。顶点已编号 1,\ldots,N。对于每个 i=1,\ldots,M, i第一条边连接顶点 a_i 和顶点 b_i。另外, 每个顶点的度数最多为 3.
对于每个 i=1,\ldots,Q,回答以下查询。
- 求与 Vertex 距离的顶点索引之和 x_i 最多 k_i.
约束
- 1 \leq N \leq 1.5 \times 10^5
- 0 \leq M \leq \min (\frac{N(N-1)}{2},\frac{3N}{2})
- 1 \leq a_i \lt b_i \leq N
- (a_i,b_i) \neq (a_j,b_j),如果 i\neq j.
- 图中每个顶点的度数最多为 3.
- 1 \leq Q \leq 1.5 \times 10^5
- 1 \leq x_i \leq N
- 0 \leq k_i \leq 3
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
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
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-st查询,距离Vertex唯一的顶点 1 最多是 1 是顶点 1,所以答案是 1.
对于 2-nd查询,距Vertex距离的顶点 2 最多 2 是顶点 2, 3, 4, 5,和 6,所以答案是它们的总和, 20.
的 3-rd 和后续查询可以类似地回答。