CF917E Upside Down

众所周知，Eleven 具备特殊能力。因此，Hopper 说服她用意念关闭通往颠倒世界的大门。颠倒世界的怪物们喜欢在两个世界间穿梭，所以它们打算攻击 Hopper 和 Eleven 以阻止他们。怪物们生活在藤蔓中。这些藤蔓构成了一棵有 $n$ 个结点的树，结点编号从 $1$ 到 $n$。每条隧道（边）上都写有一个小写英文字母。  颠倒世界是一个神奇的世界。在颠倒世界中有 $m$ 种怪物，编号从 $1$ 到 $m$。每种怪物都拥有一个赋予它力量的特殊单词。第 $i$ 种怪物的特殊单词为 $s_i$。颠倒世界共有 $q$ 只怪物，每只怪物处在某个路口（结点）上，打算前往另一个路口。如果第 $k$ 种怪物从结点 $i$ 走到结点 $j$，它获得的力量等于在所经过隧道上连续看到它的特殊单词 $s_k$ 的次数。更正式地说： 设 $f(i, j)$ 为从 $i$ 到 $j$ 的最短路径经过的隧道上的字母按顺序拼接形成的字符串，则怪物获得的力量等于 $s_k$ 在 $f(i, j)$ 中出现的次数。 Hopper 和 Eleven 想要做好准备，因此，对于每只怪物，他们都想知道该怪物移动后获得的力量。

第一行包含三个正整数 $n,m,q$（$2 \le n \le 10^5$，$1 \le m,q \le 10^5$）。 接下来 $n-1$ 行描述这棵树的隧道（边）。每行包含两个整数 $v,u$（$1 \le v,u \le n$，$v \ne u$）和一个小写英文字母 $c$，表示连接结点 $v$ 和结点 $u$ 的隧道上写有字母 $c$。保证给出的图是一棵树。 接下来的 $m$ 行，每行描述一个特殊单词。第 $i$ 行包含一个只由小写英文字母组成的字符串 $s_i$（$1 \le |s_i| \le 10^5$）。保证所有特殊单词长度之和不超过 $10^5$，即 $|s_1| + |s_2| + \cdots + |s_m| \le 10^5$。 接下来的 $q$ 行描述怪物的信息。每行包含三个整数 $i,j,k$（$1 \le i,j \le n$，$i \ne j$，$1 \le k \le m$），表示一只第 $k$ 种怪物将从结点 $i$ 走到结点 $j$。

输出 $q$ 行。第 $i$ 行输出第 $i$ 个怪物移动后获得的力量。

由 ChatGPT 5 翻译