CF1207G.Indie Album

省选/NOI-

通过率：0%

时间限制：3.00s

内存限制：512MB

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

Mishka's favourite experimental indie band has recently dropped a new album! Songs of that album share one gimmick. Each name $s_i$ is one of the following types:

$1~c$ — a single lowercase Latin letter;
$2~j~c$ — name $s_j$ ( $1 \le j \lt i$ ) with a single lowercase Latin letter appended to its end.

Songs are numbered from $1$ to $n$ . It's guaranteed that the first song is always of type $1$ .

Vova is rather interested in the new album but he really doesn't have the time to listen to it entirely. Thus he asks Mishka some questions about it to determine if some song is worth listening to. Questions have the following format:

$i~t$ — count the number of occurrences of string $t$ in $s_i$ (the name of the $i$ -th song of the album) as a continuous substring, $t$ consists only of lowercase Latin letters.

Mishka doesn't question the purpose of that information, yet he struggles to provide it. Can you please help Mishka answer all Vova's questions?

米什卡最喜爱的实验性独立乐队最近发布了一张新专辑！这张专辑中的歌曲名有一个共同的特点：每个歌名 $s_i$ 属于以下两种类型之一：

$1~c$ —— 一个单独的小写拉丁字母；
$2~j~c$ —— 将第 $j$ 首歌的歌名 $s_j$ （其中 $1 \le j \lt i$ ）末尾追加一个单独的小写拉丁字母 $c$ 所构成的字符串。

歌曲编号从 $1$ 到 $n$ 。题目保证第一首歌的类型一定是 $1$ 。

沃瓦对这张新专辑很感兴趣，但他实在没有时间完整地听一遍。因此他向米什卡提出了一些问题，以判断某首歌是否值得一听。问题的格式如下：

$i~t$ —— 计算字符串 $t$ 在 $s_i$ （即专辑中第 $i$ 首歌的歌名）中作为连续子串出现的次数；其中 $t$ 仅由小写拉丁字母组成。

米什卡并不质疑这些信息的意义，但他却难以给出答案。你能帮米什卡回答沃瓦的所有问题吗？

输入格式

The first line contains a single integer $n$ ( $1 \le n \le 4 \cdot 10^5$ ) — the number of songs in the album.

Each of the next $n$ lines contains the desciption of the $i$ -th song of the album in the following format:

$1~c$ — $s_i$ is a single lowercase Latin letter;
$2~j~c$ — $s_i$ is the name $s_j$ ( $1 \le j \lt i$ ) with a single lowercase Latin letter appended to its end.

The next line contains a single integer $m$ ( $1 \le m \le 4 \cdot 10^5$ ) — the number of Vova's questions.

Each of the next $m$ lines contains the desciption of the $j$ -th Vova's question in the following format:

$i~t$ ( $1 \le i \le n$ , $1 \le |t| \le 4 \cdot 10^5$ ) — count the number of occurrences of string $t$ in $s_i$ (the name of the $i$ -th song of the album) as a continuous substring, $t$ consists only of lowercase Latin letters.

It's guaranteed that the total length of question strings $t$ doesn't exceed $4 \cdot 10^5$ .

第一行包含一个整数 $n$ （ $1 \le n \le 4 \cdot 10^5$ ）—— 表示专辑中歌曲的数量。

接下来的 $n$ 行，每行描述专辑中第 $i$ 首歌曲 $s_i$ ，格式如下：

$1~c$ — $s_i$ 是单个小写拉丁字母；
$2~j~c$ — $s_i$ 是第 $j$ 首歌曲的名称 $s_j$ （其中 $1 \le j \lt i$ ）后追加一个单个小写拉丁字母所得。

下一行包含一个整数 $m$ （ $1 \le m \le 4 \cdot 10^5$ ）—— 表示 Vova 提出的问题数量。

接下来的 $m$ 行，每行描述 Vova 的第 $j$ 个问题，格式如下：

$i~t$ （其中 $1 \le i \le n$ ， $1 \le |t| \le 4 \cdot 10^5$ ）—— 计算字符串 $t$ 在 $s_i$ （专辑中第 $i$ 首歌曲的名称）中作为连续子串出现的次数； $t$ 仅由小写拉丁字母组成。

保证所有问题中字符串 $t$ 的总长度不超过 $4 \cdot 10^5$ 。

输出格式

For each question print a single integer — the number of occurrences of the question string $t$ in the name of the $i$ -th song of the album as a continuous substring.

对于每个问题，输出一个整数——问题字符串 $t$ 在专辑中第 $i$ 首歌曲名称中作为连续子串出现的次数。

输入输出样例

输入#1

20
1 d
2 1 a
2 2 d
2 3 a
2 4 d
2 5 a
2 6 d
2 7 a
1 d
2 9 o
2 10 k
2 11 i
2 12 d
2 13 o
2 14 k
2 15 i
2 1 o
2 17 k
2 18 i
2 15 i
12
8 da
8 dada
8 ada
6 dada
3 dada
19 doki
19 ok
16 doki
15 doki
9 d
1 a
20 doki

输出#1

说明/提示

Song names of the first example:

d
da
dad
dada
dadad
dadada
dadadad
dadadada
d
do
dok
doki
dokid
dokido
dokidok
dokidoki
do
dok
doki
dokidoki

Thus the occurrences for each question string are:

string "da" starts in positions $[1, 3, 5, 7]$ in the name "dadadada";
string "dada" starts in positions $[1, 3, 5]$ in the name "dadadada";
string "ada" starts in positions $[2, 4, 6]$ in the name "dadadada";
string "dada" starts in positions $[1, 3]$ in the name "dadada";
no occurrences of string "dada" in the name "dad";
string "doki" starts in position $[1]$ in the name "doki";
string "ok" starts in position $[2]$ in the name "doki";
string "doki" starts in positions $[1, 5]$ in the name "dokidoki";
string "doki" starts in position $[1]$ in the name "dokidok";
string "d" starts in position $[1]$ in the name "d";
no occurrences of string "a" in the name "d";
string "doki" starts in positions $[1, 5]$ in the name "dokidoki".

第一个样例的歌曲名称：

d
da
dad
dada
dadad
dadada
dadadad
dadadada
d
do
dok
doki
dokid
dokido
dokidok
dokidoki
do
dok
doki
dokidoki

因此，每个查询字符串的出现位置为：

字符串 "da" 在歌曲名 "dadadada" 中起始于位置 $[1, 3, 5, 7]$ ；
字符串 "dada" 在歌曲名 "dadadada" 中起始于位置 $[1, 3, 5]$ ；
字符串 "ada" 在歌曲名 "dadadada" 中起始于位置 $[2, 4, 6]$ ；
字符串 "dada" 在歌曲名 "dadada" 中起始于位置 $[1, 3]$ ；
字符串 "dada" 在歌曲名 "dad" 中无出现；
字符串 "doki" 在歌曲名 "doki" 中起始于位置 $[1]$ ；
字符串 "ok" 在歌曲名 "doki" 中起始于位置 $[2]$ ；
字符串 "doki" 在歌曲名 "dokidoki" 中起始于位置 $[1, 5]$ ；
字符串 "doki" 在歌曲名 "dokidok" 中起始于位置 $[1]$ ；
字符串 "d" 在歌曲名 "d" 中起始于位置 $[1]$ ；
字符串 "a" 在歌曲名 "d" 中无出现；
字符串 "doki" 在歌曲名 "dokidoki" 中起始于位置 $[1, 5]$ 。

输入解题思路，AI测评打分。不知道怎么写?

首页