Abbyy Cup 2.0 - Финал (неоф. трансляция) |
---|
Закончено |
Умному Бобру из ABBYY пришла идея новой развивающей игры для детей. Бобер считает, что такая игра поможет детям лучше понимать программирование.
Основной объект игры — конечные корневые деревья, на каждом ребре которых записана некоторая строчная буква латинского алфавита. Вершины в любом дереве всегда пронумерованы последовательно от 1 до m, где m — число вершин в этом дереве. Перед описанием самой игры введем несколько определений.
Последовательность вершин дерева с номерами v1, v2, ..., vk (k ≥ 1) будем называть прямым путем, если для любого целого i от 1 до k - 1 вершина vi является непосредственным предком вершины vi + 1. Если мы последовательно выпишем все буквы по ребрам данного пути от v1 до vk, то мы получим некоторую строку (при k = 1 — пустую). Будем говорить, что такая строка соответствует прямому пути v1, v2, ..., vk.
Последовательность вершин дерева с номерами v1, v2, ..., vk (k ≥ 1) будем называть обратным путем, если для любого целого i от 1 до k - 1 вершина vi является непосредственным потомком вершины vi + 1. Если мы последовательно выпишем все буквы по ребрам данного пути от v1 до vk, то мы получим некоторую строку (при k = 1 — пустую). Будем говорить, что такая строка соответствует обратному пути v1, v2, ..., vk.
Теперь опишем игру, которую придумал Умный Бобер из ABBYY. Для игры используются два корневых дерева, каждое из которых изначально состоит из одной вершины с номером 1. Игроку дана некоторая последовательность операций. Каждая операция характеризуется тройкой (t, v, c), где:
Сама операция заключается в следующем: у вершины v дерева t появляется новый потомок с номером m + 1 (где m — текущее число вершин в дереве t), причем на ребре, которое входит в новую вершину, нужно записать букву c.
Упорядоченную тройку целых чисел (i, j, q) будем называть хорошей комбинацией, если:
Ваша задача заключается в том, чтобы вычислить количество существующих хороших комбинаций после каждой операции над деревьями.
В первой строке содержится целое число n — количество операций над деревьями. Следующие n строк содержат описания операций в порядке их выполнения. Каждая строка имеет вид «t v c», где t — номер дерева, v — номер вершины в дереве, c — строчная буква латинского алфавита.
Для получения полного балла за первую группу тестов достаточно решить задачу при 1 ≤ n ≤ 700.
Для получения полного балла за вторую группу тестов достаточно решить задачу при 1 ≤ n ≤ 7000.
Для получения полного балла за третью группу тестов достаточно решить задачу при 1 ≤ n ≤ 100000.
Выведите ровно n строк по одному целому числу в каждой — количество существующих хороших комбинаций после соответствующей операции из ввода.
Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-битных чисел на С++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d.
5
1 1 a
2 1 a
1 2 b
2 1 b
2 3 a
1
3
3
4
7
После первой операции единственная хорошая комбинация — (1, 1, 1). После второй операции появились новые хорошие комбинации (2, 1, 2) и (1, 2, 2). Третья операция не принесла никаких хороших комбинаций. После четвёртой операции появилась хорошая комбинация (1, 3, 3). Наконец, после пятой операции появилось сразу три новых хороших комбинации — (1, 4, 4), (2, 3, 4) и (3, 1, 4).
Название |
---|