AT_kupc2019_l タケノコ

[problemUrl]: https://atcoder.jp/contests/kupc2019/tasks/kupc2019_l **これはインタラクティブな問題です。** $ 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\

入力は以下の形式で標準入力から与えられる。 > $ Q $ $ x_0 $ $ y_0 $ $ Query_1 $ $ Query_2 $ $ : $ $ Query_Q $ $ Query_i(1\ \leq\ i\ \leq\ Q) $ は問題文にある $ 3 $ 種類のいずれかの形式で与えられる。

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

### 制約 - $ 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 $ を超えない。 - 入力は全て整数である。 ### 入出力の注意 - この問題は **インタラクティブな問題** である。クエリ $ 3 $ ごとに答えを出力しない限り、それ以降の入力が与えられない。 - 出力の最後には改行を含めて出力しなければならない。そのあと、標準出力をflushしなければならない。そうでないときは `TLE` の可能性がある。 - 出力の形式が間違っている場合の挙動は定義されていない。（`WA` とは限らない。） - **この問題ではインタラクティブの都合上、言語にかかわらず入出力が最悪ケースでは少なくとも $ 4 $ sec 程度かかるので実行時間制限に注意せよ。** ### Sample Explanation 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 $ になります。タケノコの高さが負でもすいばか君への見え方は問題文中に書いてある通りであることに注意してください。