CF291E.Tree-String Problem

A rooted tree is a non-directed connected graph without any cycles with a distinguished vertex, which is called the tree root. Consider the vertices of a rooted tree, that consists of n vertices, numbered from 1 to n. In this problem the tree root is the vertex number 1.

Let's represent the length of the shortest by the number of edges path in the tree between vertices v and u as d(v, u).

A parent of vertex v in the rooted tree with the root in vertex r (v ≠ r) is vertex p__v, such that d(r, p__v) + 1 = d(r, v) and d(p__v, v) = 1. For example, on the picture the parent of vertex v = 5 is vertex _p_5 = 2.

One day Polycarpus came across a rooted tree, consisting of n vertices. The tree wasn't exactly ordinary: it had strings written on its edges. Polycarpus positioned the tree on the plane so as to make all edges lead from top to bottom if you go from the vertex parent to the vertex (see the picture). For any edge that lead from vertex p__v to vertex v (1 < v ≤ n), he knows string s__v that is written on it. All strings are written on the edges from top to bottom. For example, on the picture _s_7="ba". The characters in the strings are numbered starting from 0.

An example of Polycarpus's tree (corresponds to the example from the statement)

Polycarpus defines the position in this tree as a specific letter on a specific string. The position is written as a pair of integers (v, x) that means that the position is the x-th letter of the string s__v (1 < v ≤ n, 0 ≤ x < |s__v|), where |s__v| is the length of string s__v. For example, the highlighted letters are positions (2, 1) and (3, 1).

Let's consider the pair of positions (v, x) and (u, y) in Polycarpus' tree, such that the way from the first position to the second goes down on each step. We will consider that the pair of such positions defines string z. String z consists of all letters on the way from (v, x) to (u, y), written in the order of this path. For example, in the picture the highlighted positions define string "bacaba".

Polycarpus has a string t, he wants to know the number of pairs of positions that define string t. Note that the way from the first position to the second in the pair must go down everywhere. Help him with this challenging tree-string problem!

一棵有根树是一棵无向连通图，不含任何环，且其中有一个被特别指定的顶点，称为树的根。考虑一棵包含 $n$ 个顶点的有根树，其顶点编号为 $1$ 到 $n$。本题中，树的根固定为顶点 $1$。

记 $d(v, u)$ 为树中顶点 $v$ 与 $u$ 之间最短路径（按边数计）的长度。

在以顶点 $r$ 为根的有根树中，顶点 $v$（$v \ne r$）的父节点是指顶点 $p_v$，满足 $d(r, p_v) + 1 = d(r, v)$ 且 $d(p_v, v) = 1$。例如，在图中，顶点 $v = 5$ 的父节点是 $p_5 = 2$。

某日，Polycarpus 遇到一棵包含 $n$ 个顶点的有根树。这棵树并非普通树：它的每条边上都写有一个字符串。Polycarpus 将树置于平面上，使得所有边均从上至下延伸（即从父节点指向子节点的方向，参见图示）。对于任意一条从父节点 $p_v$ 指向子节点 $v$ 的边（其中 $1 < v \le n$），他已知写在该边上的字符串 $s_v$。所有字符串均按从上至下的方向书写。例如，在图中 $s_7 = \text{"ba"}$。字符串中的字符下标从 $0$ 开始编号。

Polycarpus 的树的一个示例（对应题目描述中的样例）

Polycarpus 将树中的一个位置定义为某条边上某个特定字符串中的某个特定字母。该位置用一对整数 $(v, x)$ 表示，意为：它是字符串 $s_v$ 中的第 $x$ 个字母（其中 $1 < v \le n$，且 $0 \le x < |s_v|$），这里 $|s_v|$ 表示字符串 $s_v$ 的长度。例如，图中高亮显示的字母对应位置 $(2, 1)$ 和 $(3, 1)$。

我们考虑 Polycarpus 树中的一对位置 $(v, x)$ 与 $(u, y)$，要求从第一个位置到第二个位置的路径每一步均向下（即沿父子方向）。我们称这样的一对位置定义了字符串 $z$：$z$ 是从 $(v, x)$ 到 $(u, y)$ 的路径上所经过的所有字母按顺序拼接而成的字符串。例如，在图中，高亮的位置定义了字符串 "bacaba"。

Polycarpus 有一个字符串 $t$，他想知道有多少对位置定义了字符串 $t$。注意：在该对位置中，从第一个位置到第二个位置的路径必须全程向下。请帮助他解决这个富有挑战性的树-字符串问题！

The first line contains integer n (2 ≤ n ≤ 105) — the number of vertices of Polycarpus's tree. Next n - 1 lines contain the tree edges. The i-th of them contains number p__i + 1 and string s__i + 1 (1 ≤ p__i + 1 ≤ n; p__i + 1 ≠ (i + 1)). String s__i + 1 is non-empty and consists of lowercase English letters. The last line contains string t. String t consists of lowercase English letters, its length is at least 2.

It is guaranteed that the input contains at most 3·105 English letters.

第一行包含一个整数 $n$（$2 \leq n \leq 10^5$）——表示 Polycarpus 的树的顶点数。接下来的 $n-1$ 行描述了树的边。其中第 $i$ 行包含一个整数 $p_{i+1}$ 和一个字符串 $s_{i+1}$（$1 \leq p_{i+1} \leq n$；$p_{i+1} \neq (i+1)$）。字符串 $s_{i+1}$ 非空，且仅由小写英文字母组成。最后一行包含字符串 $t$。字符串 $t$ 仅由小写英文字母组成，其长度至少为 $2$。

保证输入中包含的小写英文字母总数不超过 $3 \cdot 10^5$ 个。

Print a single integer — the required number.

Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.

输出一个整数——即所要求的数。

请注意，在 C++ 中不要使用 %lld 说明符来读取或写入 64 位整数。推荐使用 cin、cout 流，或 %I64d 说明符。

In the first test case string "aba" is determined by the pairs of positions: (2, 0) and (5, 0); (5, 2) and (6, 1); (5, 2) and (3, 1); (4, 0) and (4, 2); (4, 4) and (4, 6); (3, 3) and (3, 5).

Note that the string is not defined by the pair of positions (7, 1) and (5, 0), as the way between them doesn't always go down.

在第一个测试用例中，字符串 "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) 确定，因为它们之间的路径并非始终向下。