Корневым деревом называется неориентированный связный граф без циклов с выделенной вершиной, которая называется корнем дерева. Будем считать, что вершины корневого дерева из n вершин пронумерованы от 1 до n. В этой задаче корнем дерева будет вершина с номером 1.
Обозначим через d(v, u) длину кратчайшего по количеству ребер пути в дереве между вершинами v и u.
Родителем вершины v в корневом дереве с корнем в вершине r (v ≠ r) называется вершина pv, такая, что d(r, pv) + 1 = d(r, v) и d(pv, v) = 1. Например, на рисунке родителем вершины v = 5 является вершина p5 = 2.
Как-то раз Поликарп раздобыл корневое дерево из n вершин. Дерево было не совсем обычное — на его ребрах были написаны строки. Поликарп расположил дерево на плоскости так, что все ребра ведут сверху вниз при прохождении от родителя вершины к вершине (см. рисунок). Для каждого ребра, ведущего из вершины pv в вершину v (1 < v ≤ n), известна строка sv, которая на нем написана. Все строки записаны на ребрах сверху вниз. Например, на рисунке s7=«ba». Символы в строках пронумерованы от 0.
Пример дерева Поликарпа (соответствует примеру из условия) Позицией в этом дереве Поликарп называет конкретную букву конкретной строки. Позиция записывается как пара целых чисел (v, x), которая обозначает, что позицией является x-ая буква строки sv (1 < v ≤ n, 0 ≤ x < |sv|), где |sv| — длина строки sv. Например, выделенные буквы — это позиции (2, 1) и (3, 1).
Рассмотрим пару позиций (v, x) и (u, y) в дереве Поликарпа, такую, что путь от первой позиции ко второй идет сверху вниз в дереве Поликарпа, нарисованном на плоскости. Будем считать, что пара этих позиций определяет строку z. Строка z состоит из всех букв на пути от (v, x) к (u, y), записанных в порядке прохождения этого пути. Например, на рисунке выделенные позиции определяют строку «bacaba».
У Поликарпа есть строка t, он хочет узнать, сколько существует пар позиций, которые определяют строку t. Обратите внимание, что путь от первой позиции ко второй в паре должен всюду вести вниз. Помогите ему с этой нелегкой древесно-строковой задачей!
В первой строке задано целое число n (2 ≤ n ≤ 105) — количество вершин дерева Поликарпа. В следующих n - 1 строках заданы ребра дерева. В i-ой из них записаны число pi + 1 и строка si + 1 (1 ≤ pi + 1 ≤ n; pi + 1 ≠ (i + 1)). Строка si + 1 — непустая и состоит из строчных букв латинского алфавита. В последней строке записана строка t. Строка t состоит из строчных букв латинского алфавита, ее длина не менее 2.
Гарантируется, что входные данные содержат не более 3·105 букв латинского алфавита.
Выведите единственное целое число — искомое количество.
Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-х битовых чисел на С++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d
7
1 ab
5 bacaba
1 abacaba
2 aca
5 ba
2 ba
aba
6
7
1 ab
5 bacaba
1 abacaba
2 aca
5 ba
2 ba
bacaba
4
В первом тестовом примере строку «aba» определяют пары позиций: (2, 0) и (5, 0); (5, 2) и (6, 1); (5, 2) и (3, 1); (4, 0) и (4, 2); (4, 4) и (4, 6); (3, 3) и (3, 5).
Обратите внимание, что эту строку не определяет пара позиций (7, 1) и (5, 0), потому как путь между ними не всегда идет вниз.
