#x1009. CF1608G Alphabetic Tree

    ID: 6107 远端评测题 3000ms 256MiB 尝试: 4 已通过: 0 难度: 10 上传者: 标签>CF2900省选/NOI-后缀数组倍增计数排序树上倍增LCA哈希表二分查找离线查询树状数组

CF1608G Alphabetic Tree

Alphabetic Tree

题面翻译

给定 mm 个仅包含小写字母的字符串和一棵包含 nn 个节点的树,树的每条边上都有一个小写字母。我们定义 str(u,v)str(u,v) 为将在树上从 uu 到 vv 的路径上经过的所有边上的小写字母顺此拼接得到的字符串。你需要回答 qq 次询问,每次询问给定 44 个整数 u,v,l,ru,v,l,r,你需要回答在所有下标在 [l,r][l,r] 的字符串中,str(u,v)str(u,v) 出现了多少次。

数据范围:

  • 2⩽n⩽1052\leqslant n\leqslant 10^5,1⩽m,q⩽1051\leqslant m,q\leqslant 10^5。
  • 1⩽u,v⩽n1\leqslant u,v\leqslant n,u≠vu\neq v,1⩽l⩽r⩽m1\leqslant l\leqslant r\leqslant m。

Translated by Eason_AC

题目描述

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

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

输入格式

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

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

It's guaranteed that these edges form a tree.

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

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

输出格式

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

样例 #1

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

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