CF1608G Alphabetic Tree

给定 $m$ 个字符串和一棵有 $n$ 个节点的树。每条边上都写有一个字母。 你需要回答 $q$ 个询问。每个询问由 $4$ 个整数 $u$、$v$、$l$ 和 $r$ 描述。对于每个询问，答案是字符串 $str(u,v)$ 在下标从 $l$ 到 $r$ 的字符串中出现的总次数。$str(u,v)$ 定义为：从 $u$ 到 $v$ 的最短路径上，依次连接经过的边上的字母所得到的字符串。

输入的第一行包含三个整数 $n$、$m$ 和 $q$（$2 \le n \le 10^5$，$1 \le m,q \le 10^5$）。 接下来的 $n-1$ 行中，第 $i$ 行包含两个整数 $u_i, v_i$ 和一个小写拉丁字母 $c_i$（$1 \le u_i, v_i \le n$，$u_i \neq v_i$），表示在 $u_i$ 和 $v_i$ 之间有一条边，边上写有字符 $c_i$。 保证这些边构成一棵树。 接下来的 $m$ 行，每行一个仅包含小写拉丁字母的字符串。所有字符串的总长度不超过 $10^5$。 接下来 $q$ 行，每行包含四个整数 $u$、$v$、$l$ 和 $r$（$1 \le u,v \le n$，$u \neq v$，$1 \le l \le r \le m$），表示一个询问。

对于每个询问，输出一个整数，表示答案。

由 ChatGPT 4.1 翻译