← 返回题目列表

Codeforces · 917/E

E. 颠倒

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

众所周知,十一拥有特殊能力。于是,霍珀说服她用意念关闭了颠倒世界的大门。颠倒的怪物喜欢在世界之间移动,所以他们要攻击霍珀和十一,以阻止他们。怪物住在藤蔓里。这些藤蔓形成一棵有 n 个顶点的树,编号从 1 到 n。每个隧道(边缘)上都写有一个小写英文字母。

颠倒是一个神奇的世界。颠倒的怪物有 m 种,编号从 1 到 m。每种类型的怪物都有一个特殊的词赋予它们力量。类型i的特殊词是si。颠倒有q个怪物。每个节点都位于一个交汇点(顶点),并将前往另一个交汇点。如果类型k的怪物从结点i走到结点j,它获得的力量就是它在隧道中连续看到它的特殊世界(sk)的次数。更正式地说:

如果f(i, j)是我们将隧道中写的字母按照从i到j的最短路径连接起来得到的字符串,那么怪物获得的力量就是f(i, j)中sk出现的次数。

霍珀和十一想要做好准备,因此对于每个怪物,他们想知道怪物移动后获得的力量。

输入

输入的第一行包含三个整数,n、m 和 q (2 ≤ n ≤ 105, 1 ≤ m, q ≤ 105)。

接下来的 n - 1 行包含隧道(边缘)。每行包含两个整数v和u(1≤v,u≤n,v≠u)和一个小写英文字母c,表示有一条隧道连接v和u交叉点,其中写为c。保证给定的图是一棵树。

接下来的 m 行包含特殊单词。其中第 i 行包含单个字符串 si (1 ≤ |si| ≤ 105),由小写英文字母组成。保证|s1| + |s2| + ... + |sm| ≤ 105)。

接下来的 q 行包含怪物。每行包含三个整数 i、j 和 k(1 ≤ i、j ≤ n、i ≠ j、1 ≤ k ≤ m),这意味着类型 k 的怪物将从编号 i 的节点移动到编号 j 的节点。

输出

打印 q 行。第 i 行应包含一个整数,即第 i 个怪物在移动后获得的力量。

示例

输入 #1

6 4 5
1 6 b
2 3 a
1 2 b
5 3 b
4 5 b
a
b
bb
aa
1 2 1
6 2 3
1 6 2
4 5 4
1 6 2

输出 #1

0
1
1
0
1

输入 #2

10 6 7
1 3 s
10 1 d
2 6 s
5 2 d
7 4 l
8 9 d
8 10 l
7 2 d
8 7 l
dl
dssld
d
d
l
sl
4 5 4
3 7 5
10 6 2
3 1 4
7 5 6
10 9 4
9 8 4

输出 #2

2
2
0
0
0
1
1