102544: [AtCoder]ABC254 E - Small d and k
Description
Score : $500$ points
Problem Statement
We have a simple undirected graph with $N$ vertices and $M$ edges. The vertices are numbered $1,\ldots,N$. For each $i=1,\ldots,M$, the $i$-th edge connects Vertex $a_i$ and Vertex $b_i$. Additionally, the degree of each vertex is at most $3$.
For each $i=1,\ldots,Q$, answer the following query.
- Find the sum of indices of vertices whose distances from Vertex $x_i$ are at most $k_i$.
Constraints
- $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)$, if $i\neq j$.
- The degree of each vertex in the graph is at most $3$.
- $1 \leq Q \leq 1.5 \times 10^5$
- $1 \leq x_i \leq N$
- $0 \leq k_i \leq 3$
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
$N$ $M$ $a_1$ $b_1$ $\vdots$ $a_M$ $b_M$ $Q$ $x_1$ $k_1$ $\vdots$ $x_Q$ $k_Q$
Output
Print $Q$ lines. The $i$-th line should contain the answer to the $i$-th query.
Sample Input 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
Sample Output 1
1 20 2 20 7 6 20
For the $1$-st query, the only vertex whose distance from Vertex $1$ is at most $1$ is Vertex $1$, so the answer is $1$.
For the $2$-nd query, the vertices whose distances from Vertex $2$ are at most $2$ are Vertex $2$, $3$, $4$, $5$, and $6$, so the answer is their sum, $20$.
The $3$-rd and subsequent queries can be answered similarly.
Input
题意翻译
给定 $ n $ 个点 $ m $ 条边的简单无向图,特别地,**保证每个点的度数不超过** $ 3 $。$ q $ 次询问,给定 $ x, k $,求所有距离 $ x $ 不超过 $ k $ 的点(包括 $ x $)的编号和。Output
分数:500分
问题描述
我们有一个简单的无向图,包含$N$个顶点和$M$条边。顶点编号为$1,\ldots,N$。对于每个$i=1,\ldots,M$,第$i$条边连接顶点$a_i$和顶点$b_i$。另外,每个顶点的度数最多为3。
对于每个$i=1,\ldots,Q$,回答以下查询。
- 找出距离顶点$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$
- 如果$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$
- 输入中的所有值都是整数。
输入
输入从标准输入以以下格式给出:
$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个查询,距离顶点1不超过1的唯一顶点是顶点1,所以答案是1。
对于第2个查询,距离顶点2不超过2的顶点是顶点2、3、4、5和6,所以答案是它们的和,20。
第3个及以后的查询可以类似地回答。