Alphabetic Tree

题意翻译

给定 $m$ 个仅包含小写字母的字符串和一棵包含 $n$ 个节点的树，树的每条边上都有一个小写字母。我们定义 $str(u,v)$ 为将在树上从 $u$ 到 $v$ 的路径上经过的所有边上的小写字母顺此拼接得到的字符串。你需要回答 $q$ 次询问，每次询问给定 $4$ 个整数 $u,v,l,r$，你需要回答在所有下标在 $[l,r]$ 的字符串中，$str(u,v)$ 出现了多少次。 数据范围： - $2\leqslant n\leqslant 10^5$，$1\leqslant m,q\leqslant 10^5$。 - $1\leqslant u,v\leqslant n$，$u\neq v$，$1\leqslant l\leqslant r\leqslant m$。 Translated by Eason_AC

题目描述

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).

输入输出格式

输入格式

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.

输出格式

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

输入输出样例

输入样例 #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