← 返回题目列表

Codeforces · 291/E

E. 树串问题

中文机器翻译题面 查看原题

有根树是一种没有任何环的无向连通图,具有一个可区分的顶点,称为树根。考虑一棵有根树的顶点,它由 n 个顶点组成,编号从 1 到 n。在这个问题中,树根是顶点号 1。

让我们用树中顶点 v 和 u 之间的边数表示最短路径的长度为 d(v, u)。

根在顶点 r (v ≠ r) 的有根树中,顶点 v 的父节点是顶点 pv,因此 d(r, pv) + 1 = d(r, v) 且 d(pv, v) = 1。例如,在图片上,顶点 v = 5 的父节点是顶点 p5 = 2。

有一天,Polycarpus 遇到了一棵有根树,由 n 个顶点组成。这棵树并不普通:它的边缘写着绳子。 Polycarpus 将树放置在平面上,以便从顶点父级到顶点时,所有边都从上到下(见图)。对于从顶点 pv 到顶点 v (1 < v ≤ n) 的任何边,他都知道写在其上的字符串 sv。所有字符串均从上到下写在边缘上。例如图片上的 s7="ba"。字符串中的字符从0开始编号。

Polycarpus 树的示例(对应于声明中的示例)

Polycarpus 将此树中的位置定义为特定字符串上的特定字母。该位置被写为一对整数 (v, x),这意味着该位置是字符串 sv 的第 x 个字母(1 < v ≤ n, 0 ≤ x < |sv|),其中 |sv|是字符串 sv 的长度。例如,突出显示的字母是位置 (2, 1) 和 (3, 1)。

让我们考虑 Polycarpus 树中的一对位置 (v, x) 和 (u, y),这样从第一个位置到第二个位置的路径在每个步骤中都会下降。我们将认为一对这样的位置定义了字符串 z。字符串 z 由 (v, x) 到 (u, y) 途中的所有字母组成,按该路径的顺序写入。例如,在图片中突出显示的位置定义字符串“bacaba”。

Polycarpus 有一个字符串 t,他想知道定义字符串 t 的位置对的数量。请注意,从第一个位置到第二个位置的路径必须始终向下。帮助他解决这个具有挑战性的树绳问题!

输入

第一行包含整数 n (2 ≤ n ≤ 105) — Polycarpus 树的顶点数。接下来的 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 说明符。

示例

输入 #1

7
1 ab
5 bacaba
1 abacaba
2 aca
5 ba
2 ba
aba

输出 #1

6

输入 #2

7
1 ab
5 bacaba
1 abacaba
2 aca
5 ba
2 ba
bacaba

输出 #2

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) 定义的,因为它们之间的路径并不总是向下。