bzoj#P4545. DQS的trie
DQS的trie
题目描述
DQS 的自家阳台上种着一棵颗粒饱满、颜色纯正的 trie。
DQS 的 trie 非常的奇特,它初始有 个节点, 条边,每条边上有一个字符。并且,它拥有极强的生长力:某个 时刻,某个节点就会新生长出一颗子树,它拥有 个节点且节点之间的边上有一个字符,并且新生长出来的子树也是一个树结构。然而因为是新长出来的,根据生活常识可知 必定不会大于 时刻之前的树的大小。
DQS定义 trie 的子串为从根节点( 号节点)往下走到所有节点所构成的字符串的所有的后缀。DQS 身为一个单身 doge,常常取出其中一个子串送给妹子,然而他并不希望送给妹子两个相同的子串,所以他非常关心当前 trie 的本质不同的子串数目。
DQS 有时还会去商店购买子串,若他在商店看上某个子串,他希望得知这个子串是否在自家阳台的 trie 上已经出现,若出现则出现了多少次。如果出现了,他就可以直接回家取 trie 上的子串辣!
然而 DQS 身为一个蒟蒻,看着自家阳台的 trie 树一天天在长大,他被如此众多的节点弄得眼花缭乱,于是他找到了 IOI2016Au 的你。他会告诉你自家 trie 树的成长历程,他希望你能够对于每一次询问都做出正确回复。
输入格式
第一行输入一个整数 ,代表测试点编号。
接下来一行输入一个整数 ,表示初始树的大小。
接下来 行,每行两个整数 和一个字符 ,表示 号节点和 号节点之间有一条边,边上的字母为 。
接下来输入 ,表示有 组操作。
对于每一组,第一行输入一个整数 。
若 ,则是一组询问,询问当前 trie 的本质不同的子串数目是多少。
若 ,则后面跟两个整数 ,表示以点 为根向下长出一个子树,大小为 。
接下来 行,每行两个整数 和一个字符 ,表示 号节点和 号节点之间有一条边,边上的字母为 。若长出子树之前当前树的大小是 ,则这 个点的编号分别为 。
若 ,则是一组询问,后面输入一个字符串 ,询问字符串 在当前 trie 中的出现次数。
输出格式
对于每个 或 ,输出一行表示答案。
样例输入
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
样例说明
第一个询问,本质不同的子串是 。
第二个询问,本质不同的子串是 $\texttt{a},\texttt{b},\texttt{c},\texttt{ab},\texttt{ac},\texttt{bb},\texttt{abb}$。
第三个询问, 出现次数是 。
第四个询问,本质不同的子串是 $\texttt{a},\texttt{b},\texttt{c},\texttt{ab},\texttt{ac},\texttt{ca},\texttt{cb},\texttt{bb},\texttt{abb},\texttt{aca},\texttt{acb}$。
或 时对原树不做修改,只是询问。
每次 ,会增加 个节点,因为有一个节点是原树上作为新树的根出现的。
数据规模与约定
数据中,对于链的部分分,满足端点为根节点,每次新建子树都从尾部插入。
对于全部数据,保证从始至终每条边上的字符均为小写字母 或 或 。
设 是最终树的大小,, 不超过当前树的大小。
题目来源
By Loi_DQS