CF291E Tree-String Problem

一棵有根树是一个无向连通且无环的图，并指定一个特殊的顶点作为树根。考虑一棵包含 $n$ 个顶点的有根树，顶点编号从 1 到 $n$。在本题中，树根是编号为 1 的顶点。 记 $d(v,u)$ 表示在树中从顶点 $v$ 到顶点 $u$ 的最短路径长度（即经过的边数）。 对于树根为 $r$ 的有根树中，顶点 $v$ 的父亲定义为顶点 $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 \leq n)$ 的每一条边，已知该边上写着字符串 $s_{v}$。所有字符串都是自上而下写在边上的。例如，图片中 $s_{7}$ 为 "ba"。字符串中的字符编号从 0 开始。  在 Polycarpus 的树中，位置由字符串上的某一个具体字母确定。一个位置记作二元组 $(v,x)$，表示该位置是字符串 $s_{v}$ 的第 $x$ 个字母（$1 < v \leq n$，$0 \leq 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$。注意，两位置之间的路径必须始终朝下。 请帮助他解决这个具有挑战性的树与字符串问题！

第一行输入一个整数 $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} \ne i+1)$。字符串 $s_{i+1}$ 非空，仅包含小写英文字母。最后一行给出字符串 $t$，满足 $|t| \geq 2$，仅含小写英文字母。 保证所有输入的英文字符总数不超过 $3 \times 10^{5}$。

输出一个整数，表示所需的对数。 注意，请不要在 C++ 中使用 %lld 格式符来输入输出 64 位整数，推荐使用 cin/cout 流或 %I64d 格式符。

在第一个测试点中，由如下位置对定义的字符串均为 "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) 这一对不合法，因为它们之间的路径并非一直向下。 由 ChatGPT 5 翻译