Problem
ある時、コンスタンチンは次の、すでに第13回国際オリンピックに参加しており、電車で帰国していた。彼はいつものように、座って人生の意味について考え、同時にプログラミングの問題を解決していました。しばらくして、コンスタンチンは居眠りをしてしまいましたが、問題は、目を覚ますためには、頭に浮かんだ、彼を悩ませている問題を解決しなければならないということです。
今回、コンスタンチンは、最初は番号 1 の頂点が 1 つだけで構成されていたツリーを夢見ていました。彼が設定した問題では、新しい頂点が徐々にツリーに追加されました。 i 番目の秒では、番号 i+1 の頂点がツリーに追加され、頂点 p
i から子として吊り下げられ、頂点 i+1 間のエッジに追加されました。そして p
i という文字 c
i が書かれました
木のルートから頂点 v までの各パスは、現在のパスの端に書かれた記号をルートから頂点 v までの順序で書き出したある文字列に対応します。 Konstantin は、一見すると難しいタスクに直面しました。新しい頂点を追加するたびに、ツリーのルート (頂点番号 1) から始まり、他の頂点で終わる一意の文字列の数を数えます。
夢の中で、コンスタンチンはまったく天才ではないので、彼自身はこの問題を解決できません。コンスタンチンが問題を解決して目を覚ますのを手伝ってください。
入力:
最初の行には、数値 n が含まれています。これは、ツリーに新しいノードを追加するリクエストの数です (1 <= n <= 300000)。
次の n 行は、頂点を追加するためのリクエストを記述します。 i 番目のクエリはパラメータ p
i (1 <= p
i <= i) と c
i で記述されます。追加された番号 i+1 の頂点は、子として番号 p
i の頂点から吊り下げられ、その結果生じるエッジにシンボル c
i が書き込まれることを意味します -ラテンアルファベットの小文字
。
出力:
n 行を印刷します。 i 行目には、i+1 番目の頂点を追加した後のコンスタンチンの問題の答えを出力します。
例:
<本体>
| 入力 |
出力 |
2
1b
2 人 |
1
2 |
3
1時
1時
2 j |
1
1
2 |