Ağacla oyun#11055
Səyahət edərək oyunlar kainatında, Ralf və Vanilopa heyrətamiz bir oyun kəşf etdilər. Bu oyunda çox sürətli hesablama aparmaq lazımdır ki, bu da onlara çox xoş gəldi. Oyunun hərəkəti sehrli alma ağacının ətrafında baş verir.
Əvvəlcə alma ağacı yalnız bir alma - kökdən ibarətdir. Bu almanın nömrəsi 1-ə bərabərdir. Bundan sonra Ralf yeni bir alma əlavə edir, onu mövcud olanla bir budaq vasitəsilə bağlayır. Hər budağa Ralf a-dan z-ə qədər latın əlifbasının bir hərfini yazır.
Vanilopa isə bəzən müəyyən bir almanı qoparır. Almayla birlikdə onu bağlayan budaq da yox olur. Zəmanət verilir ki, Vanilopa tərəfindən qoparılan almaya başqa heç bir alma asılmayıb.
Kökdən almaya gedən budaqlardakı hərflərin ardıcıllığını söz adlandıraq. Sözün içində ardıcıl gələn hərflərin qeyri-boş miqdarını alt söz adlandıraq.
Hər bir hərəkətdən sonra müxtəlif alt sözlərin sayını hesablamaq lazımdır. Alt sözlər müxtəlif sayılır, əgər mövqelərdə fərqli hərflər varsa.
Birinci sırada hərəkətlərin sayı q (1 ≤ q ≤ 100000) verilir. Sonrakı q sıranın hər biri aşağıdakı formatda hərəkətlərin təsvirini ehtiva edir:
1 p c (1 ≤ p ≤ n) - Ralf hələ istifadə olunmamış minimal müsbət nömrəli almanı əlavə edir. Yeni almanın əcdadı alma p-dir və budağa latın hərfi c yazılmışdır.
2 v - Vanilopa nömrəsi v olan almanı qoparır. Zəmanət verilir ki, kök alma qoparılmayacaq və heç bir alma iki dəfə qoparılmayacaq.
Hər bir hərəkətdən sonra müxtəlif alt sözlərin sayını çıxarın.
Birinci əməliyyatdan sonra söz "a" var. Müxtəlif alt sözlər: "a".
İkinci əməliyyatdan sonra sözlər "a", "b". Müxtəlif alt sözlər: "a", "b".
Üçüncü əməliyyatdan sonra sözlər "a", "b", "a". Müxtəlif alt sözlər: "a", "b".
Dördüncü əməliyyatdan sonra sözlər "a", "b", "ac". Müxtəlif alt sözlər: "a", "b", "ac", "c".
Beşinci əməliyyatdan sonra sözlər "a", "ac". Müxtəlif alt sözlər: "a", "ac", "c".
Nümunə 1