← 返回题目列表

Codeforces · 1608/G

G. 字母树

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

给你 $$$m$$$ 字符串和 $$$n$$$ 节点上的树。每条边上都写有一些字母。

您必须回答 $$$q$$$ 查询。每个查询由 $$$4$$$ 整数 $$$u$$$、$$$v$$$、$$$l$$$ 和 $$$r$$$ 描述。查询的答案是索引从 $$$l$$$ 到 $$$r$$$ 的字符串中 $$$str(u,v)$$$ 出现的总数。 $$$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$$$),表示查询。

输出

对于每个查询,打印一个整数 - 查询的答案。

示例

输入 #1

2 5 3
1 2 a
aab
abab
aaa
b
a
2 1 1 5
1 2 1 3
2 1 3 5

输出 #1

8
7
4

输入 #2

9 5 6
1 2 a
2 7 c
1 3 b
3 4 b
4 6 b
3 5 a
5 8 b
5 9 c
ababa
cabbb
bac
bbbac
abacaba
2 7 1 4
2 5 1 5
6 3 4 4
6 9 4 5
5 7 3 5
5 3 1 5

输出 #2

3
4
2
1
1
10