Upside Down
Contest: Codeforces Round 459 (Div. 1)
Difficulty rating: 3400
Tags: data structures, string suffix structures, strings, trees

As we all know, Eleven has special abilities. Thus, Hopper convinced her to close the gate to the Upside Down World with her mind. Upside down monsters like to move between the worlds, so they are going to attack Hopper and Eleven in order to make them stop. The monsters live in the vines. The vines form a tree with n vertices, numbered from 1 through n. There's a lowercase English letter written in each tunnel (edge).

Upside down is a magical world. There are m types of monsters in upside down, numbered from 1 through m. Each type of monster has a special word that gives them powers. The special word of type i is si. There are q monsters in upside down. Each one is at a junction (vertex) and is going to some other junction. If monster of type k goes from junction i to junction j, the power it gains is the number of times it sees its special world (sk) consecutively in the tunnels. More formally:

If f(i, j) is the string we get when we concatenate the letters written in the tunnels on the shortest path from i to j, then the power the monster gains is the number of occurrences of sk in f(i, j).

Hopper and Eleven want to get prepared, so for each monster, they want to know the power the monster gains after moving.

Input format:
The first line of input contains three integers, n, m and q (2 ≤ n ≤ 105, 1 ≤ m, q ≤ 105).

The next n - 1 lines contain the tunnels (edges). Each line contains two integers v and u (1 ≤ v, u ≤ n, v ≠ u) and a lowercase English letter c, meaning there's a tunnel connecting junctions v and u written c in it. It is guaranteed that the given graph is a tree.

The next m lines contain the special words. i-th line of them contains a single string si (1 ≤ |si| ≤ 105), consisting of lowercase English letters. It is guaranteed that |s1| + |s2| + ... + |sm| ≤ 105).

The next q lines contain the monsters. Each line contains three integers i, j and k (1 ≤ i, j ≤ n, i ≠ j, 1 ≤ k ≤ m), meaning a monster of type k is going from junction number i to junction number j.

Output format:
Print q lines. i-th line should contain a single integer, the power the i-th monster gains after moving.

Constraints:
Time limit: 3.0 s
Memory limit: 512.0 MB

Example input:
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

Example output:
0
1
1
0
1

Example input:
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

Example output:
2
2
0
0
0
1
1

Editorial:
Assume ti is reverse of si. Use centroid-decomposition. When solving the problem for subtree S, assume its centroid is c. For a fixed query, assume v and u are both in S and path from v to u goes through the centroid c (this happens exactly one time for each v and u). Assume x is string of path from c to v and y is string of path from c to u. We should find the number of occurrences of sk in reverse(x) + y. If number of occurrences of s in t is f(s, t) then f(sk, reverse(x) + y) = f(tk, x) + f(sk, y) + A. First two variables can be calculated using aho-corasick and segment tree.
A is the number of occurrences of sk in the path such that some part of it belongs to reverse(x) and some to y.
So, so far the the time complexity is $${\mathcal {O}}(n\log ^{2}(n))$$.
Now for counting A, first calculate the suffix tree for each string (for each sk and tk). A suffix tree is a trie, so let sf(v, s) be the vertex we reach when we ask the string of path from c (root) to v one by in the suffix tree of string s. We can calculate this fast for every v and s if we merge this suffix trees into one trie (we do this before we start the centroid-decomposition algorithm in per-process).
We associate a value val to each vertex of the trie, initially zero for every vertex. Now we traverse this trie like DFS. When we reach a vertex x, we iterate over all suffixes (there are 2(|s1| + ... + |sn|) suffixes) that end in x (the suffixes that equal the string of path from root of the trie to vertex x), and for each suffix (s, k) (suffix of string s with length k), we add 1 to the val of each vertex in the subtree of the vertex where the suffix (reverese(s), |s| - k) ends and we subtract this number when we're exiting vertex x (in DFS).
Now back to the centroid-decomposition, A equals val of vertex in trie where the suffix (tk, b) when in DFS we're at vertex in trie where (sk, a) ends where a is the size of the longest suffix of sk that is a prefix of the string of the path from c (root) to u and similarly, b is the size of the longest suffix of tk that is a prefix of the string of the path from c (root) to v. For achieving this goal, we can use persistent segment tree on the starting time-finishing time range of vertices in the trie (or without using persistent segment tree, we could calculate every A after the centroid-decomposition is finished, kind of offline).
Total time complexity: $${\mathcal {O}}(N\log ^{2}(N))$$ where N = n + q + |s1| + |s2| + ... + |sn|.