G - Minimum Reachable City Editorial /

Time Limit: 3 sec / Memory Limit: 1024 MB

配点 : 600 点

問題文

N 頂点の有向グラフ G_S があり、頂点には 1 から N までの番号が付けられています。 G_S には N-1 本の辺があり、i 本目 (1\leq i \leq N-1) の辺は頂点 p_i\ (1\leq p_i \leq i) から頂点 i+1 に伸びています。

N 頂点の有向グラフ G があり、頂点には 1 から N までの番号が付けられています。 最初、G は G_S と一致しています。 G に関するクエリが Q 個与えられるので、与えられた順番に処理してください。クエリは次の 2 種類のいずれかです。

  • 1 u v : G に頂点 u から頂点 v に伸びる辺を追加する。 このとき、以下の条件が満たされることが保証される。
    • u \neq v
    • G_S 上で頂点 v からいくつかの辺を辿ることで頂点 u に到達可能である
  • 2 x : G 上で頂点 x からいくつかの辺を辿ることで到達可能な頂点 (頂点 x を含む) のうち、最も番号が小さい頂点の番号を出力する。

制約

  • 2\leq N \leq 2\times 10^5
  • 1\leq Q \leq 2\times 10^5
  • 1\leq p_i\leq i
  • 1 番目の形式のクエリについて、
    • 1\leq u,v \leq N
    • u \neq v
    • G_S 上で頂点 v からいくつかの辺を辿ることで頂点 u に到達可能である
  • 2 番目の形式のクエリについて、1\leq x \leq N
  • 入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

N
p_1 p_2 \dots p_{N-1}
Q
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q

ただし、\mathrm{query}_i は i 個目のクエリを表しており、次のいずれかの形式で与えられる。

1 u v

2 x

出力

2 番目の形式のクエリの回数を q 回として、q 行出力せよ。 j\ (1\leq j \leq q) 行目には、2 番目の形式のクエリのうち j 個目のものに対する答えを出力せよ。

入力例 1

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

出力例 1

4
2
1
  • 1 個目のクエリの時点で、G 上で頂点 4 からいくつかの辺を辿ることで到達可能な頂点は 4 のみです。
  • 3 個目のクエリの時点で、G 上で頂点 4 からいくつかの辺を辿ることで到達可能な頂点は 2,3,4, 5 です。
  • 5 個目のクエリの時点で、G 上で頂点 4 からいくつかの辺を辿ることで到達可能な頂点は 1,2,3,4,5 です。

入力例 2

7
1 1 2 2 3 3
10
2 5
1 5 2
2 5
1 2 1
1 7 1
1 6 3
2 5
2 6
2 1
1 7 1

出力例 2

5
2
1
1
1

Score : 600 points

Problem Statement

We have a directed graph G_S with N vertices numbered 1 to N. It has N-1 edges. The i-th edge (1\leq i \leq N-1) goes from vertex p_i\ (1\leq p_i \leq i) to vertex i+1.

We have another directed graph G with N vertices numbered 1 to N. Initially, G equals G_S. Process Q queries on G in the order they are given. There are two kinds of queries as follows.

  • 1 u v : Add an edge to G that goes from vertex u to vertex v. It is guaranteed that the following conditions are satisfied.
    • u \neq v.
    • On G_S, vertex u is reachable from vertex v via some edges.
  • 2 x : Print the smallest vertex number of a vertex reachable from vertex x via some edges on G (including vertex x).

Constraints

  • 2\leq N \leq 2\times 10^5
  • 1\leq Q \leq 2\times 10^5
  • 1\leq p_i\leq i
  • For each query in the first format:
    • 1\leq u,v \leq N.
    • u \neq v.
    • On G_S, vertex u is reachable from vertex v via some edges.
  • For each query in the second format, 1\leq x \leq N.
  • All values in the input are integers.

Input

The input is given from Standard Input in the following format:

N
p_1 p_2 \dots p_{N-1}
Q
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q

Here, \mathrm{query}_i denotes the i-th query and is in one of the following formats:

1 u v

2 x

Output

Print q lines, where q is the number of queries in the second format. The i-th line (1\leq j \leq q) should contain the answer to the j-th query in the second format.

Sample Input 1

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

Sample Output 1

4
2
1
  • At the time of the first query, only vertex 4 is reachable from vertex 4 via some edges on G.
  • At the time of the third query, vertices 2, 3, 4, and 5 are reachable from vertex 4 via some edges on G.
  • At the time of the fifth query, vertices 1, 2, 3, 4, and 5 are reachable from vertex 4 via some edges on G.

Sample Input 2

7
1 1 2 2 3 3
10
2 5
1 5 2
2 5
1 2 1
1 7 1
1 6 3
2 5
2 6
2 1
1 7 1

Sample Output 2

5
2
1
1
1