Гра з деревом#11055
Під час подорожі всесвітом ігор, Ральф і Ванілопа натрапили на захопливу гру, яка вимагає швидкого підрахунку, що їм дуже сподобалося. Події гри розгортаються навколо чарівної яблуні.
Спочатку на яблуні є лише одне яблуко — корінь, з номером . Потім Ральф додає нове яблуко, прикріплюючи його до вже існуючого за допомогою гілки. На кожній гілці Ральф пише літеру латинського алфавіту від a до z.
Ванілопа іноді зриває певне яблуко. Разом з яблуком зникає і гілка, що його тримала. Гарантується, що жодне інше яблуко не підвішене до яблука, яке зриває Ванілопа.
Словом назвемо послідовність літер на гілках від кореня до яблука. Підсловом є непорожня послідовність підряд розташованих літер у слові.
Ваше завдання — після кожної дії визначити кількість різних підслів. Підслова вважаються різними, якщо вони відрізняються хоча б на одній позиції.
У першому рядку знаходиться кількість дій (1 \leq q \leq 100000). Кожен з наступних рядків містить опис дії у форматі:
1 p c (1 \leq p \leq n) — означає, що Ральф додає нове яблуко з найменшим позитивним номером, який ще не використовувався. Предком нового яблука є яблуко , а на гілці написана літера .
2 v — Ванілопа зриває яблуко з номером . Гарантується, що кореневе яблуко не буде зірвано, і жодне яблуко не буде зірвано двічі.
Після кожної дії виведіть кількість різних підслів.
Приклад 1
Після першої операції є слово "a". Різні підслова: "a".
Після другої операції слова "a", "b". Різні підслова: "a", "b".
Після третьої операції слова "a", "b", "a". Різні підслова: "a", "b".
Після четвертої операції слова "a", "b", "ac". Різні підслова: "a", "b", "ac", "c".
Після п'ятої операції слова "a", "ac". Різні підслова: "a", "ac", "c".