Alphabetic Tree
Contest: Codeforces Round 758 (Div.1 + Div. 2)
Difficulty rating: 3500
Tags: binary search, data structures, dfs and similar, hashing, string suffix structures, strings, trees

You are given $$$m$$$ strings and a tree on $$$n$$$ nodes. Each edge has some letter written on it.

You have to answer $$$q$$$ queries. Each query is described by $$$4$$$ integers $$$u$$$, $$$v$$$, $$$l$$$ and $$$r$$$. The answer to the query is the total number of occurrences of $$$str(u,v)$$$ in strings with indices from $$$l$$$ to $$$r$$$. $$$str(u,v)$$$ is defined as the string that is made by concatenating letters written on the edges on the shortest path from $$$u$$$ to $$$v$$$ (in order that they are traversed).

Input format:
The first line of the input contains three integers $$$n$$$, $$$m$$$ and $$$q$$$ ($$$2 \le n \le 10^5$$$, $$$1 \le m,q \le 10^5$$$).

The $$$i$$$-th of the following $$$n-1$$$ lines contains two integers $$$u_i, v_i$$$ and a lowercase Latin letter $$$c_i$$$ ($$$1 \le u_i, v_i \le n$$$, $$$u_i \neq v_i$$$), denoting the edge between nodes $$$u_i, v_i$$$ with a character $$$c_i$$$ on it.

It's guaranteed that these edges form a tree.

The following $$$m$$$ lines contain the strings consisting of lowercase Latin letters. The total length of those strings does not exceed $$$10^5$$$.

Then $$$q$$$ lines follow, each containing four integers $$$u$$$, $$$v$$$, $$$l$$$ and $$$r$$$ ($$$1 \le u,v \le n$$$, $$$u \neq v$$$, $$$1 \le l \le r \le m$$$), denoting the queries.

Output format:
For each query print a single integer — the answer to the query.

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

Example input:
2 5 3
1 2 a
aab
abab
aaa
b
a
2 1 1 5
1 2 1 3
2 1 3 5

Example output:
8
7
4

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

Example output:
3
4
2
1
1
10

Editorial:
Let's concatenate the $$$m$$$ input strings, separated by some character not in the input, into a string $$$S$$$, and build the suffix array over it. If we could lexicographically compare $$$str(u, v)$$$ to some suffix of $$$S$$$, we could use binary search to find the left and right boundary of suffixes that start with $$$str(u, v)$$$ in the suffix array.
Knowing how to find the longest common prefix of a path in the tree and a suffix of $$$S$$$ would help us in comparing them, since we would know the first position where these string differ.
Letters on the tree are still unrelated to the letters in concatenated string, so let's append them to $$$S$$$ in some helpful way. Let's split the tree into chains using heavy-light decomposition and append the chains and reversed chains to the string $$$S$$$. This way every path in the tree can be split into $$$O(logn)$$$ parts which are substrings of $$$S$$$.
Let's build LCP array of $$$S$$$ from it's suffix array, and then sparse table over the LCP array, to be able to answer queries for longest common prefix of two suffixes of $$$S$$$ in $$$O(1)$$$. With such queries we can get longest common prefix of a path and a suffix of $$$S$$$ in $$$O(logn)$$$ by querying LCP for $$$O(logn)$$$ parts of the path and corresponding suffixes of $$$S$$$.
Now we know how to find the range of suffixes which have $$$str(u, v)$$$ as a prefix. Out of these suffixes we have to count only these for which first position belongs to a string with index in the set $$$\{l, l+1, \dots, r \}$$$.
We can do the counting offline, sweeping through strings from the first to the last and maintaining binary indexed tree over suffix array. In iteration $$$i$$$ we store $$$1$$$ for suffixes of strings with indices $$$1, 2, \dots, i$$$, and $$$0$$$ for the rest. A query can be solved by taking the difference of sums on suffix array range in iteration $$$r$$$ and in iteration $$$l-1$$$.
Building suffix array can be done in $$$O(nlog^2n)$$$, $$$O(nlogn)$$$ or $$$O(n)$$$ depending on the chosen algorithm, LCP array can be constructed from the suffix array in $$$O(n)$$$ using Kasai's algorithm, while the sparse table construction works in $$$O(nlogn)$$$ and uses $$$O(nlogn)$$$ memory. Searching for the ranges can be done in $$$O(qlog^2n)$$$ as described above, and the last offline sweeping part takes $$$O((n+q)logn)$$$ time. The overall time complexity is $$$O((n+q)log^2n)$$$, with $$$O(nlogn)$$$ memory.