CF1045J.Moonwalk challenge

Since astronauts from BubbleCup XI mission finished their mission on the Moon and are big fans of famous singer, they decided to spend some fun time before returning to the Earth and hence created a so called "Moonwalk challenge" game.

Teams of astronauts are given the map of craters on the Moon and direct bidirectional paths from some craters to others that are safe for "Moonwalking". Each of those direct paths is colored in one color and there is unique path between each two craters. Goal of the game is to find two craters such that given array of colors appears most times as continuous subarray on the path between those two craters (overlapping appearances should be counted).

To help your favorite team win, you should make a program that, given the map, answers the queries of the following type: For two craters and array of colors answer how many times given array appears as continuous subarray on the path from the first crater to the second.

Colors are represented as lowercase English alphabet letters.

由于 BubbleCup XI 任务的宇航员已在月球上圆满完成任务，且他们都是某位著名歌手的忠实粉丝，因此决定在返回地球前轻松一下，于是设计了一个名为“月面漫步挑战”（Moonwalk Challenge）的游戏。

宇航员队伍会获得一张月球陨石坑地图，以及若干条连接某些陨石坑的、适合“月面漫步”的双向安全路径。每条直接路径均被染成一种颜色，且任意两个陨石坑之间存在唯一路径。游戏的目标是：找出两个陨石坑，使得给定的颜色数组作为连续子数组，在这两陨石坑之间的路径上出现的次数最多（重叠的出现也需分别计数）。

为了帮助你最喜爱的队伍获胜，你需要编写一个程序：给定该地图，对如下类型的查询作出回答——对于两个陨石坑及一个颜色数组，求该颜色数组作为连续子数组在从第一个陨石坑到第二个陨石坑的路径上出现的次数。

颜色用小写英文字母表示。

In the first line, integer $N$ $(2 \leq N \leq 10^5)$ — number of craters on the Moon. Craters are numerated with numbers $1$ to $N$.

In next $N-1$ lines, three values $u, v, L$ $(1 \leq u, v \leq N, L \in {a, ..., z})$ — denoting that there is a direct path with color $L$ between craters $u$ and $v$.

Next line contains integer $Q$ $(1 \leq Q \leq 10^5)$ — number of queries.

Next $Q$ lines contain three values $u, v$ $(1 \leq u, v \leq N)$ and $S$ $(|S| \leq 100)$, where $u$ and $v$ are the two cratersfor which you should find how many times array of colors $S$ (represented as string) appears on the path from $u$ to $v$.

第一行包含一个整数 $N$（$2 \leq N \leq 10^5$），表示月球上的环形山数量。环形山编号为 $1$ 到 $N$。

接下来的 $N-1$ 行，每行包含三个值 $u, v, L$（$1 \leq u, v \leq N$，$L \in \{a, \dots, z\}$），表示环形山 $u$ 与 $v$ 之间存在一条颜色为 $L$ 的直接路径。

下一行包含一个整数 $Q$（$1 \leq Q \leq 10^5$），表示查询次数。

接下来的 $Q$ 行，每行包含三个值 $u, v$（$1 \leq u, v \leq N$）和字符串 $S$（$|S| \leq 100$），其中 $u$ 和 $v$ 是待查询的两个环形山，你需要计算字符串 $S$ 所表示的颜色序列在从 $u$ 到 $v$ 的路径上出现了多少次。

For each query output one number that represents number of occurrences of array S on the path from $u$ to $v$.

对于每个查询，输出一个数字，表示数组 $S$ 在从 $u$ 到 $v$ 的路径上出现的次数。