#1037. 一棵树

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: tony102

题目描述

从前有一棵树,树上的每条边上都有一个小写字母。

次这样的询问:每次指出树上的两点 并给出一个由小写字母构成的字符串 ,询问串 中出现了多少次,其中 表示树上从点 到点 的唯一路径上每条边上的小写字母顺次连接形成的字符串。

注意

输入格式

第一行两个正整数

接下来 行,每行两个正整数 和一个小写字母 ,表示一条树边 ,这条树边上的小写字母是

接下来 行,每两行表示一次询问。对于每次询问,第一行两个正整数 ,第二行一个由小写字符构成的字符串 ,意义详见题目描述。

输出格式

输出 行表示每次询问的答案。

样例

见附加文件

数据范围与提示

,即输入的询问串总长度。

对于 的数据,

对于 的数据,

对于 的数据,

对于 的数据,