408807: GYM103328 D String Repetition

Given a rooted tree of $$$N$$$ nodes with lowercase English characters on its nodes. Note here that node number $$$1$$$ is always the root of the tree.

There are $$$Q$$$ queries to be processed. Each query gives a node $$$u_j$$$ and a string $$$t_j$$$, asking how many times $$$t_j$$$ appears on the path from the root to $$$u_j$$$. The strings are read from top to bottom if we regard the root as the top-most node. In particular, a string $$$t$$$ is said to appear on the path from the root to a node $$$u$$$ if there exists a sequence of nodes $$$p_1, p_2, \ldots, p_{|t|}$$$ such that

• $$$p_i$$$ is the father of $$$p_{i + 1}$$$, for $$$1 \leq i < |t|$$$.
• The character written on $$$p_i$$$ is the same as the $$$i$$$-th character of $$$t$$$, for all $$$1 \leq i \leq |t|$$$.
• $$$p_{|t|}$$$ is an ancestor of $$$u$$$ (including $$$u$$$ itself).

Two appearances are considered different if their corresponding node sequences are different.

The first line consists of a single integer $$$N$$$, the number of nodes on the tree.

The second line consists of a string $$$s$$$ of length $$$N$$$, representing the characters on the tree. The $$$i$$$-th character in $$$s$$$ is the character on the $$$i$$$-th node.

The following $$$N-1$$$ lines describe the tree. Each of the lines consists of two integers $$$a_i, b_i$$$, meaning that there is an edge connecting the $$$a_i$$$-th node and the $$$b_i$$$-th node.

The $$$N+2$$$-th line consists of a single integer $$$Q$$$, the number of queries.

The following $$$Q$$$ lines are the queries. Each of the lines consists of an integer $$$u_j$$$ and a string $$$t_j$$$.

• $$$1 \leq N, Q \leq 3 \times 10^{5}$$$
• $$$1 \leq a_i, b_i, u_i \leq N$$$
• $$$1 \leq \sum_{j=1}^{q} |t_j| \leq 3 \times 10^{5}$$$
• The given input forms a tree
• All characters are lowercase English characters

For each query, output a single line consists of a single integer, the answer to the query.

4
aaaa
1 2
2 3
1 4
20
1 a
1 aa
1 aaa
1 aaaa
1 b
2 a
2 aa
2 aaa
2 aaaa
2 b
3 a
3 aa
3 aaa
3 aaaa
3 b
4 a
4 aa
4 aaa
4 aaaa
4 b

1
0
0
0
0
2
1
0
0
0
3
2
1
0
0
2
1
0
0
0

5
abcde
1 2
2 3
3 4
3 5
4
4 abcd
4 bc
5 ecba
5 cb

1
1
0
0