BZPRO

#4545. DQS的trie

内存限制：256 MiB 时间限制：10 Sec
提交 提交记录 讨论

题目描述

DQS的自家阳台上种着一棵颗粒饱满、颜色纯正的trie。
DQS的trie非常的奇特，它初始有n0个节点，n0-1条边，每条边上有一个字符。并且，它拥有极强的生长力：某个i时刻，某个节点就会新生长出一颗子树，它拥有si个节点且节点之间的边上有一个字符，并且新生长出来的子树也是一个树结构。然而因为是新长出来的，根据生活常识可知si必定不会大于i时刻之前的树的大小。
DQS定义trie的子串为从根节点（1号节点）往下走到所有节点所构成的字符串的所有的后缀。DQS身为一个单身doge，常常取出其中一个子串送给妹子，然而他并不希望送给妹子两个相同的子串，所以他非常关心当前trie的本质不同的子串数目。
DQS有时还会去商店购买子串，若他在商店看上某个子串，他希望得知这个子串是否在自家阳台的trie上已经出现，若出现则出现了多少次。如果出现了，他就可以直接回家取trie上的子串辣！
然而DQS身为一个蒟蒻，看着自家阳台的trie树一天天在长大，他被如此众多的节点弄得眼花缭乱，于是他找到了IOI2016Au的你。他会告诉你自家trie树的成长历程，他希望你能够对于每一次询问都做出正确回复。

输入格式

第一行输入一个整数id，代表测试点编号。
接下来一行输入一个整数n0，表示初始树的大小。
接下来n0-1行，每行两个整数u,v和一个字符c，表示u号节点和v号节点之间有一条边，边上的字母为c。
接下来输入m表示有m组操作。
对于每一组，第一行输入一个整数opt。
若opt=1，则是一组询问，询问当前trie的本质不同的子串数目是多少。
若opt=2，则后面跟两个整数rt,si，表示以点rt为根向下长出一个子树，大小为si。
接下来si-1行，每行两个整数u,v和一个字符c，表示u号节点和v号节点之间有一条边，边上的字母为c。若长出子树之前当前树的大小是n，则这si-1点的编号分别为n+1,n+2…n+si-1。
若opt=3，则是一组询问，后面输入一个字符串S，询问字符串S在当前trie中的出现次数。 

输出格式

对于每个opt=1或3，输出一行表示答案。

样例

样例输入


			
1

4

1 2 a 

1 3 b

2 4 b

6

1

2 2 4

2 5 b

2 6 c 

5 7 b

1

3 ab

2 6 3

6 8 a

6 9 b

1

样例输出


			
3

7

2

11



【数据范围及提示】

第一个询问，本质不同的子串是 a,b,ab。

第二个询问，本质不同的子串是 a,b,c,ab,ac,bb,abb。

第三个询问，ab出现次数是 2。

第四个询问，本质不同的子串是 a,b,c,ab,ac,ca,cb,bb,abb,aca,acb。

opt=1或3时对原树不做修改，只是询问。

每次opt=2，会增加si-1个节点，因为有一个节点是原树上作为新树的根出现的。

数据中，对于链的部分分，满足端点为根节点，每次新建子树都从尾部插入。

对于全部数据，保证从始至终每条边上的字符均为小写字母’a’或’b’或’c’。

n是最终树的大小,N<=100000,M<=100000,Si<=当前树的大小

数据范围与提示

BZPRO Powered by Remmina.
Github Repository