【讨厌的新系统】

题目描述

最近,某公司推出了一种新的 PC 操作系统 Swodniw vista 。于是,小恒便高高兴兴地将它买了回来,并给自己的计算机撞上了。结果他发现许多软件和程序的运行速度都慢了很多,和以前的操作系统相比,简直就是天壤之别。后来小恒发现,原来是新系统的 UAC 保护模式在作怪。

UAC 保护模式其实就是一个用户权限检测系统。每当一个用户执行一条操作,UAC 都会花上若干时间来检测合法性。UAC 将检测分成了 N 个模块,每个模块的执行顺序严格按照一个有向树拓扑有序,如下图所示:

 

该有向树的意义为:你需要完成某个检测,必须在该检测之前,完成其在树上的父亲检测。

一个模块包含两个属性,匹配串 S 和检测时间 C 。现在,对一个操作串 T ,当一个模块的S包含了 T 中的某个字符,则必须执行该模块。要注意,可以同时执行的多个模块,但要保证完成了父亲模块,才能开始儿子模块的检测。

比如,对操作系列“BE”,则执行了 A、B、C、D、E 五个模块,最少话费时间为 6(1+3+2)。

现在给出 M 个操作串,那么 UAC 完成每个串的检测最少需要多少时间呢?

输入格式

第1行为两个整数 N 和 M(N≤2007,M≤100000),N 表示检测个数,M 表示操作串个数。
接下来 N 行,每行包含非负整数 F 和 C(C≤1000)和一个字符串 S(S长度≤100),分别表示前继模块的序号,检测时间和匹配串。模块由 1 到 N 编号,根的前继为 0 。
再下来 M 行,每行只有一个字符串(长度≤100),表示需要检测的操作串。
字符串中不包含空格、换行符和所有的控制字符。

输出格式

输出 M 行,每行包含一个整数,分别表示每个操作串最少的检测时间。

样例数据 1

输入

6 2
0 1 ABCDEF
1 3 ABC
2 2 BC
1 1 DEF
4 1 D
1 4 AEF
BE
AA

输出

6
5

样例数据 2

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

输出

3
1

样例数据 3

输入

6 2
0 1 ABCDEF
1 3
2 2 BC
1 1 DEF
4 1 D
1 4 AEF

AA

输出

0
5

样例数据 4

输入

3 3
3 20 oGd?avaPnJ?C+Osf))<4<k/xaK+![o%Q;1uN4SERc&^&t_
2 32 (yP]pI5Z$9rH^?2,zcy;v#1|q76<uP8r
0 100 /N5c7\/V;0Qe|C)az{fdcgyv+1X:PVc?Xft=%
fkghb7[-dc2w400DOgy,PeW=TZmW^dS9Jd.BE
h{Inob’n?$kSY/z?fGc
[=@+

输出

120
120
120

备注

【数据范围】
对于 40% 的数据:N,M≤1000;
对于 100% 的数据:N≤2007;M≤100000。
所有匹配串和操作串都不含空格。

注意样例有空格!如果遇到这种情况直接输出0即可。普通的暴力能拿40分,可以分析一下它的问题,因为暴力每次都要重新找一遍,而对于一个字符它在有根树里的花费是唯一的,也就是说我们可以把找到的结果存下来,以后直接找即可,这样可以大幅度优化掉原来N*M的暴力变为接近N*100的复杂度,因为ASCII码表里最多不超过100个字符,对100个字符暴力一遍后就是O1查询了。这种记忆化暴力的方法对其他类似题也很有用。

下面是代码:

 

stdKonjac

stdKonjac

一只挣扎的蒟蒻ACMer

评论太激烈有些评论需要亲动动手指翻页

留下你的评论

*评论支持代码高亮<pre class="prettyprint linenums">代码</pre>

*