#4231. 回忆树

题目描述

回忆树是树。

具体来说，是n个点n-1条边的无向连通图，点标号为1~n，每条边上有一个字符（出于简化目的，我们认为只有小写字母）。

对一棵回忆树来说，回忆当然是少不了的。

一次回忆是这样的：你想起过往，触及心底…唔,不对，我们要说题目。

这题中我们认为回忆是这样的：给定2个点u，v(u可能等于v)和一个非空字符串s，问从u到v的简单路径上的所有边按照到u的距离从小到大的顺序排列后，边上的字符依次拼接形成的字符串中给定的串s出现了多少次。

输入格式

第一行2个整数，依次为树中点的个数n和回忆的次数m。

接下来n-1行，每行2个整数u、v和1个小写字母c，表示回忆树的点u、v之间有一条边，边上的字符为c

接下来2m行表示m次回忆，每次回忆2行：第1行2个整数u、v，第2行给出回忆的字符串s。

输出格式

对于每次回忆，输出串s出现的次数。

样例

样例输入

12 3  

1 2 w  

2 3 w  

3 4 x  

4 5 w  

5 6 w  

6 7 x  

7 8 w  

8 9 w  

9 10 x  

10 11 w  

11 12 w  

1 7  

wwx  

1 12  

www  

1 12  

w

样例输出

2  

0  

8

数据范围与提示

对于100%的数据，n<=100000,m<=100000,询问串的总长<=300000