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
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$$$.
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
Name |
---|