L - タケノコ Editorial /

Time Limit: 7 sec / Memory Limit: 1024 MB

配点 : 500

問題文

これはインタラクティブな問題です。

1 つの頂点からなる根付き木 T があり、この頂点を頂点 0 とします。頂点 0 には、長さ x_0 で伸びやすさが y_0 のタケノコが生えています。

また、頂点 0 にはすいばか君がいます。

Q 個のクエリが与えられるので順番に処理してください。クエリは 3 種類あり、以下の形式で与えられます。

  • クエリ 1 : 1 v x y ― 頂点 v を親とする長さ x で伸びやすさが y のタケノコが生えた新しい頂点を追加せよ。新しい頂点の番号はこの直前に追加された頂点番号(ない場合は 0 + 1 とする。
  • クエリ 2 : 2 a ― すいばか君が根付き木 T 全体に効果 a の肥料を散布する。これにより根付き木 T の任意の頂点に生えているタケノコは、現在の長さが x で伸びやすさが y とすると長さが x + a \times y に変わる。
  • クエリ 3 : 3 v ― すいばか君に頂点 v までの単純パス上(両端を含む)に見えているタケノコの本数を尋ねる。すいばか君は 30 本以下のタケノコは正確に数えて答えることができるが、31 本以上は数えるのがめんどくさくなってしまうため many と答える。あなたはこの答えを予想して出力せよ。

ただし、すいばか君にタケノコ t が見えているとは、頂点 0 からタケノコ t の生えている頂点までの単純パス上(両端を含む)の頂点に生えているタケノコの高さを順番に h_1, h_2, ..., h_n とするとき、h_i < h_n (1 \leq i \leq n - 1) を満たすことを指します。また、すいばか君に頂点 0 のタケノコは見えています。

制約

  • 1 \leq Q \leq 2 \times 10^5
  • 1 \leq x_0 \leq 10^9
  • 1 \leq y_0 \leq 10^6
  • 0 \leq v \leq (最後に追加された頂点番号(ない場合は 0 ))
  • 1 \leq x \leq 10^9
  • 1 \leq y \leq 10^6
  • -10^6 \leq a \leq 10^6
  • クエリ 3 の数は 3 \times 10^4 を超えない。
  • 入力は全て整数である。

入力

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

Q x_0 y_0
Query_1
Query_2
:
Query_Q

Query_i(1 \leq i \leq Q) は問題文にある 3 種類のいずれかの形式で与えられる。

出力

クエリ 3 ごとに答えを出力せよ。

入出力の注意

  • この問題は インタラクティブな問題 である。クエリ 3 ごとに答えを出力しない限り、それ以降の入力が与えられない。
  • 出力の最後には改行を含めて出力しなければならない。そのあと、標準出力をflushしなければならない。そうでないときは TLE の可能性がある。
  • 出力の形式が間違っている場合の挙動は定義されていない。(WA とは限らない。)
  • この問題ではインタラクティブの都合上、言語にかかわらず入出力が最悪ケースでは少なくとも 4 sec 程度かかるので実行時間制限に注意せよ。

入力例 1

4 1 1
1 0 2 2
3 1
2 -2
3 1

出力例 1

2
1
  • 1 つ目のクエリでは、頂点 0 を親とする頂点 1 が追加されます。頂点 1 のタケノコは高さ 2 で伸びやすさ 2 です。
  • 2 つ目のクエリでは、頂点 0, 1 のタケノコのうちすいばか君が見えるものを数えます。頂点 0, 1 のタケノコの高さはそれぞれ 1, 2 であり、すいばか君には両方のタケノコが見えます。なので、答えは 2 になります。
  • 3 つ目のクエリでは、頂点 0, 1 のタケノコの高さがそれぞれ -1, -2 に変わります。このように、タケノコの高さは負になることもあります。
  • 4 つ目のクエリでは、頂点 0, 1 のタケノコのうちすいばか君が見えるものを数えます。このとき、頂点 1 のタケノコは、 (頂点 0 のタケノコの高さ) < (頂点 1 のタケノコの高さ) を満たさないため見えません。なので、答えは 1 になります。タケノコの高さが負でもすいばか君への見え方は問題文中に書いてある通りであることに注意してください。

入力例 2

12 1 1
1 0 5 1
1 1 2 3
2 1
3 2
1 2 1 5
2 2
3 3
1 2 1 1
2 -4
3 3
2 5
3 4

出力例 2

2
3
2
3

入力例 3

34 1 1
1 0 1 2
1 1 1 3
1 2 1 4
1 3 1 5
1 4 1 6
1 5 1 7
1 6 1 8
1 7 1 9
1 8 1 10
1 9 1 11
1 10 1 12
1 11 1 13
1 12 1 14
1 13 1 15
1 14 1 16
1 15 1 17
1 16 1 18
1 17 1 19
1 18 1 20
1 19 1 21
1 20 1 22
1 21 1 23
1 22 1 24
1 23 1 25
1 24 1 26
1 25 1 27
1 26 1 28
1 27 1 29
1 28 1 30
1 29 1 31
3 30
2 1
3 29
3 30

出力例 3

1
30
many