| Codeforces Round 459 (Div. 1) |
|---|
| Закончено |
Все знают, что Одиннадцать обладает некоторыми сверхспособностями. Поэтому Хоппер уговорила ее закрыть врата на Обратную сторону силой мысли. Монстры с Обратной стороны любят перемещаться между мирами, поэтому они собираются атаковать Хоппер и Одиннадцать, чтобы остановить их. Монстры живут на дереве из n вершин, пронумерованных от 1 до n. На каждом ребре написана строчная латинская буква.
Обратная сторона — магический мир. В нем живут m видов монстров, пронумерованных от 1 до m. У каждого вида монстров есть специальное слово, которое дает ему силу. Специальное слово вида i равно si. Всего на Обратной стороне q монстров. Каждый сейчас находится в одной вершине и собирается дойти до некоторой другой вершины. Если монстр типа k идет от вершины i до вершины j, его сила увеличивается на количество раз, когда он видел свое специальное слово (sk) как подстроку на своем пути. Более формально:
Пусть f(i, j) — строка, которую мы получим, если выпишем все буквы на ребрах на кратчайшем пути из i в j. Тогда сила монстра увеличивается на количество вхождений sk в f(i, j).
Хоппер и Одиннадцать хотят подготовиться, поэтому для каждого монстра они хотят определить силу, которую приобретет монстр после передвижения.
Первая строка содержит три целых числа 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-го монстра после передвижения.
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
0
1
1
0
1
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
0
0
0
1
1
