Well-defined Path Queries on a Namori

题目描述

你被给定了一个连通的简单无向图 $G$，该图有 $N$$$个顶点，编号为 $1$ 到 $N$，并且有 $N$ 条边。第 $i$ 条边双向连接顶点 $u_i$ 和顶点 $v_i$。 回答以下 $Q$ 个查询。

判断是否存在从顶点 $x_i$ 到顶点 $y_i$ 的唯一简单路径（简单路径是不重复顶点的路径）。

输入格式

输入从标准输入按照以下格式给出： $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$。

5
1 2
2 3
1 3
1 4
2 5
3
1 2
1 4
1 5

No
Yes
No

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

Yes
No
Yes
Yes
No
No
Yes
No
Yes
No

提示

$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 输入中的所有数值均为整数。从顶点 $1$ 到 $2$ 的简单路径有 $(1,2)$ 和 $(1,3,2)$，它们不是唯一的，所以第一个查询的答案是 $No$。 从顶点 $1$ 到 $4$ 的简单路径是 $(1,4)$，这是唯一的，所以第二个查询的答案是 $Yes$。 从顶点 $1$ 到 $5$ 的简单路径有 $(1,2,5)$ 和 $(1,3,2,5)$，它们不是唯一的，所以第三个查询的答案是 $No$。

标签: AtCoder|abc266F

来源

AtCoder|abc266F