102665: [AtCoder]ABC266 F - Well-defined Path Queries on a Namori
Description
Score : $500$ points
Problem Statement
You are given a connected simple undirected graph $G$ with $N$ vertices numbered $1$ to $N$ and $N$ edges. The $i$-th edge connects Vertex $u_i$ and Vertex $v_i$ bidirectionally.
Answer the following $Q$ queries.
- Determine whether there is a unique simple path from Vertex $x_i$ to Vertex $y_i$ (a simple path is a path without repetition of vertices).
Constraints
- $3 \leq N \leq 2 \times 10^5$
- $1 \leq u_i < v_i\leq N$
- $(u_i,v_i) \neq (u_j,v_j)$ if $i \neq j$.
- $G$ is a connected simple undirected graph with $N$ vertices and $N$ edges.
- $1 \leq Q \leq 2 \times 10^5$
- $1 \leq x_i < y_i\leq N$
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
$N$ $u_1$ $v_1$ $u_2$ $v_2$ $\vdots$ $u_N$ $v_N$ $Q$ $x_1$ $y_1$ $x_2$ $y_2$ $\vdots$ $x_Q$ $y_Q$
Output
Print $Q$ lines.
The $i$-th line $(1 \leq i \leq Q)$ should contain Yes
if there is a unique simple path from Vertex $x_i$ to Vertex $y_i$, and No
otherwise.
Sample Input 1
5 1 2 2 3 1 3 1 4 2 5 3 1 2 1 4 1 5
Sample Output 1
No Yes No
The simple paths from Vertex $1$ to $2$ are $(1,2)$ and $(1,3,2)$, which are not unique, so the answer to the first query is No
.
The simple path from Vertex $1$ to $4$ is $(1,4)$, which is unique, so the answer to the second query is Yes
.
The simple paths from Vertex $1$ to $5$ are $(1,2,5)$ and $(1,3,2,5)$, which are not unique, so the answer to the third query is No
.
Sample Input 2
10 3 5 5 7 4 8 2 9 1 2 7 9 1 6 4 10 2 5 2 10 10 1 8 6 9 8 10 6 8 3 10 3 9 1 10 5 8 1 10 7 8
Sample Output 2
Yes No Yes Yes No No Yes No Yes No
Input
题意翻译
### 题目描述 给定一张有 $N$ 个点、$N$ 条边的简单连通无向图和 $Q$ 次询问,对于每次询问,给定 $x_i,y_i$,表示两点的编号,请你回答第 $x_i$ 个点和第 $y_i$ 个点之间是否**有且仅有**一条简单路径。 + 什么是简单路径? 如果路径上的各顶点均不重复,则称这样的路径为简单路径。 ### 输入格式 第一行包含一个整数 $N$; 接下来 $N$ 行,每行两个整数 $u_i,v_i$,表示第 $i$ 条边连接的两个点; 再接下来一行包含一个整数 $Q$; 最后 $Q$ 行,每行两个整数 $x_i,y_i$,含义见题目描述。 ### 输出格式 对于每次询问,输出一个字符串 `Yes` 或 `No`,分别表示两点之间是否仅存在一条简单路径,每个询问分别输出一行。 ### 样例 见原题面。 ### 样例解析 样例 #1 解析: 对于第一次询问,从 $1$ 到 $2$ 有两条简单路径 $(1,2)$、$(1,3,2)$,所以输出 `No`。 对于第二次询问,从 $1$ 到 $4$ 仅有一条路径 $(1,4)$,所以输出 `Yes`。 对于第三次询问,从 $1$ 到 $5$ 有两条简单路径 $(1,2,5)$、$(1,3,2,5)$,所以输出 `No`。 ### 数据范围 对于 $30\%$ 的数据,$N \le 100$,$Q \le \frac{N(N-1)}{2}$; 对于 $100\%$ 的数据,$3 \le N \le 2 \times 10^5$,$1 \le u_i<v_i \le N$,$1 \le Q \le 2 \times 10^5$,$1 \le x_i < y_i \le N$,保证图没有重边或自环,且给定询问均不重复。 翻译 by @CarroT1212Output
分数:500分
问题描述
给你一个连接的简单无向图$G$,包含$N$个编号为$1$到$N$的顶点和$N$条边。第$i$条边连接顶点$u_i$和顶点$v_i$双向。
回答以下$Q$个查询。
- 判断是否存在从顶点$x_i$到顶点$y_i$的唯一简单路径(简单路径是不重复顶点的路径)。
约束条件
- $3 \leq N \leq 2 \times 10^5$
- $1 \leq u_i < v_i\leq N$
- $(u_i,v_i) \neq (u_j,v_j)$ if $i \neq j$。
- $G$是一个包含$N$个顶点和$N$条边的连接的简单无向图。
- $1 \leq Q \leq 2 \times 10^5$
- $1 \leq x_i < y_i\leq N$
- 输入中的所有值都是整数。
输入
输入从标准输入以以下格式给出:
$N$ $u_1$ $v_1$ $u_2$ $v_2$ $\vdots$ $u_N$ $v_N$ $Q$ $x_1$ $y_1$ $x_2$ $y_2$ $\vdots$ $x_Q$ $y_Q$
输出
输出$Q$行。
第$i$行 $(1 \leq i \leq Q)$ 应包含 Yes
,如果存在从顶点$x_i$到顶点$y_i$的唯一简单路径,否则包含 No
。
样例输入1
5 1 2 2 3 1 3 1 4 2 5 3 1 2 1 4 1 5
样例输出1
No Yes No
从顶点$1$到$2$的简单路径有$(1,2)$和$(1,3,2)$,它们不是唯一的,因此第一个查询的答案是 No
。
从顶点$1$到$4$的简单路径是$(1,4)$,它是唯一的,因此第二个查询的答案是 Yes
。
从顶点$1$到$5$的简单路径有$(1,2,5)$和$(1,3,2,5)$,它们不是唯一的,因此第三个查询的答案是 No
。
样例输入2
10 3 5 5 7 4 8 2 9 1 2 7 9 1 6 4 10 2 5 2 10 10 1 8 6 9 8 10 6 8 3 10 3 9 1 10 5 8 1 10 7 8
样例输出2
Yes No Yes Yes No No Yes No Yes No