题目详情题解（0）讨论（0）提交记录（0）

AT_abc266_f.[ABC266F] Well-defined Path Queries on a Namori

提高+/省选-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

给定一张有 NN 个点、NN 条边的简单连通无向图和 QQ 次询问，对于每次询问，给定 xi,yix_i,y_i，表示两点的编号，请你回答第 xix_i 个点和第 yiy_i 个点之间是否有且仅有一条简单路径。

  • 什么是简单路径？

如果路径上的各顶点均不重复，则称这样的路径为简单路径。

输入格式

第一行包含一个整数 NN；

接下来 NN 行，每行两个整数 ui,viu_i,v_i，表示第 ii 条边连接的两个点；

再接下来一行包含一个整数 QQ；

输出格式

对于每次询问，输出一个字符串 Yes 或 No，分别表示两点之间是否仅存在一条简单路径，每个询问分别输出一行。

样例

见原题面。

样例解析

样例 #1 解析：

对于第一次询问，从 11 到 22 有两条简单路径 (1,2)(1,2)、(1,3,2)(1,3,2)，所以输出 No。

对于第二次询问，从 11 到 44 仅有一条路径 (1,4)(1,4)，所以输出 Yes。

对于第三次询问，从 11 到 55 有两条简单路径 (1,2,5)(1,2,5)、(1,3,2,5)(1,3,2,5)，所以输出 No。

输入输出样例

  • 输入#1

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

    输出#1

    No
Yes
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

说明/提示

对于 30%30\% 的数据，N≤100N \le 100，Q≤N(N−1)2Q \le \frac{N(N-1)}{2}；

对于 100%100\% 的数据，3≤N≤2×1053 \le N \le 2 \times 10^5，1≤ui<vi≤N1 \le u_i<v_i \le N，1≤Q≤2×1051 \le Q \le 2 \times 10^5，1≤xi<yi≤N1 \le x_i < y_i \le N，保证图没有重边或自环，且给定询问均不重复。

翻译 by @CarroT1212

输入解题思路，AI测评打分。不知道怎么写?

首页