← 返回题目列表

AtCoder · past201912_k

K. 企业集团

中文机器翻译题面 查看原题

警告

在日本标准时间 2019 年 12 月 29 日凌晨 05:00 之前请勿提及此问题。如有违反,可要求赔偿。

考试结束后,您可以向其他人透露您的总分和等级,但仅此而已(例如,您解决了哪些问题)。

问题陈述

某公司有 N 会员,会员 1, \ldots, N。其中一位是总统,没有老板。其他每个成员都有一个直属老板。根据你的数据库,该会员的直属上司 i (1 \leq i \leq N) 是会员 p_i (p_i = -1 如果会员 i 是总统)。这些成员之间不存在循环关系。

基于此数据库,您想要创建一个 Web 服务,当两个数字 给出代表两个成员的 a 和 b ,判断是否为成员 a is 初级 致会员 b。在此,会员 a 据说是会员的初级 b 当且仅当会员 可以通过会员联系 b 可以通过会员联系 a 仅沿向上方向追踪成员之间的关系。

给出的是 Q 数字对 (a_1, b_1), \ldots, (a_Q, b_Q),每个代表两名成员。编写一个打印的程序 Yes or No 对于他们每个人。

约束

  • 2 \leq N \leq 150000
  • 对于每个 i = 1, \ldots, N, p_i = -1 or 1 \leq p_i \leq N.
  • 存在一个独特的 i 这样 p_i = -1.
  • 成员之间不存在循环关系。
  • 1 \leq Q \leq 100000
  • 1 \leq a_i, b_i \leq N
  • a_i \neq b_i

输入

输入由标准输入按以下格式给出:

N
p_1
p_2
:
p_N
Q
a_1 b_1
a_2 b_2
:
a_Q b_Q

输出

打印 Q 行。的 i第行 (1 \leq i \leq Q) 应包含 Yes 如果会员 a_i 的级别低于会员 b_i,和 No 否则。


示例输入 1

7
-1
1
1
2
2
3
3
6
7 1
4 1
2 3
5 1
5 2
2 5

示例输出 1

Yes
Yes
No
Yes
Yes
No

会员的直系后辈 1 (主席)是会员 2, 3,会员的直系后辈 2 是会员 4, 5,以及会员的直系后辈 3 是会员 6, 7.

例如,对于第一对 (7, 1), 会员 1 是“会员直属老板”的直属老板 7“(会员 3),所以我们打印 Yes.


示例输入 2

20
4
11
12
-1
1
13
13
4
6
20
1
1
20
10
8
8
20
10
18
1
20
18 14
11 3
2 13
13 11
10 15
9 5
17 11
18 10
1 16
9 4
19 6
5 10
17 8
15 8
5 16
6 20
3 19
10 12
5 13
18 1

示例输出 2

No
No
No
No
No
No
No
Yes
No
Yes
No
No
No
Yes
No
Yes
No
No
No
Yes