#6583. 「ICPC World Finals 2019」何以伊名始

内存限制:1024 MiB 时间限制:10000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Snakes

题目描述

众所周知,皇室家族的名字非常有讲究。而作为研究皇室的历史学家的你,最近接到了一个艰巨的任务——分析王国历史中所有皇室夫人的名字。

王国历史上有 n 位皇室夫人,方便起见,我们将其从 1 n 编号。除了 1 号夫人外,其余夫人的名字均为一个大写字母连接着她母亲的名字。而 1 号夫人作为王国的首任王后,她的名字只有一个大写字母。

例如,由于 AENERYSAENERYS 组成,因此 ENERYSAENERYS 的母亲。相似地,AENERYSDAENERYSYAENERYS 的母亲。

你知道王国历史上所有皇室夫人的姓名与关系,而你需要完成的任务是,对于其他历史学家感兴趣的名字串 s ,总共有多少位夫人的名字是以 s 起始的。

例如在样例的皇室族谱中,SAENERYS 的这一支(包含 YSRYSERYSNERYSENERYS 这几位夫人)均只有一位女儿。接下来 AENERYS 有两位女儿,分别是 DAENERYS,以及女儿是 RYAENERYSYAENERYS

在这个皇室家族内,有两位夫人的名字以 RY 起始,她们是 RYSRYAENERYS。而 ERYSENERYS 均以 E 起始。名字以 N 起始的仅有一位夫人 NERYS。同样地,以 S 起始的仅有首位王后 S。而没有任何一位夫人的名字以 AY 起始。

输入格式

第一行有两个整数 n,k ,分别代表王国历史上皇室夫人总数,以及其他历史学家感兴趣的名字串的个数。

接下来 n 行描述所有皇室夫人的姓名与关系。第 i+1 行描述第 i 位夫人的资料 c_i p_i ,其中字符 c_i 表示她名字的首位字母, p_i 为她母亲的编号。对于编号为 1 的首位王后, p_1=0 。所有夫人的名字均不重复。

接下来 k 行,每行为一个大写字母构成的非空串,代表一个其他历史学家感兴趣的名字串。

输出格式

输出 k 行,第 i 行为一个整数,代表总共有多少位夫人的名字是以第 i 个感兴趣的名字串起始的。

样例

样例输入

10 5
S 0
Y 1
R 2
E 3
N 4
E 5
A 6
D 7
Y 7
R 9
RY
E
N
S
AY

样例输出

2
2
1
1
0

数据范围与提示

1\leq n\leq 10^6 1\leq k\leq 10^6 p_1=0 ,特别地,对于 1\lt i\leq n ,保证有 1\leq p_i\lt i 。感兴趣的名字串总长不超过 10^6