bzoj#P4545. DQS的trie

DQS的trie

题目描述

DQS 的自家阳台上种着一棵颗粒饱满、颜色纯正的 trie。

DQS 的 trie 非常的奇特,它初始有 n0n_0 个节点,n01n_0-1 条边,每条边上有一个字符。并且,它拥有极强的生长力:某个 ii 时刻,某个节点就会新生长出一颗子树,它拥有 sis_i 个节点且节点之间的边上有一个字符,并且新生长出来的子树也是一个树结构。然而因为是新长出来的,根据生活常识可知 sis_i 必定不会大于 ii 时刻之前的树的大小。

DQS定义 trie 的子串为从根节点(11 号节点)往下走到所有节点所构成的字符串的所有的后缀。DQS 身为一个单身 doge,常常取出其中一个子串送给妹子,然而他并不希望送给妹子两个相同的子串,所以他非常关心当前 trie 的本质不同的子串数目。

DQS 有时还会去商店购买子串,若他在商店看上某个子串,他希望得知这个子串是否在自家阳台的 trie 上已经出现,若出现则出现了多少次。如果出现了,他就可以直接回家取 trie 上的子串辣!

然而 DQS 身为一个蒟蒻,看着自家阳台的 trie 树一天天在长大,他被如此众多的节点弄得眼花缭乱,于是他找到了 IOI2016Au 的你。他会告诉你自家 trie 树的成长历程,他希望你能够对于每一次询问都做出正确回复。

输入格式

第一行输入一个整数 id\text{id},代表测试点编号。

接下来一行输入一个整数 n0n_0,表示初始树的大小。

接下来 n01n_0-1 行,每行两个整数 u,vu,v 和一个字符 cc,表示 uu 号节点和 vv 号节点之间有一条边,边上的字母为 cc

接下来输入 mm,表示有 mm 组操作。

对于每一组,第一行输入一个整数 opt\text{opt}

opt=1\text{opt}=1,则是一组询问,询问当前 trie 的本质不同的子串数目是多少。

opt=2\text{opt}=2,则后面跟两个整数 rt,sirt,s_i,表示以点 rtrt 为根向下长出一个子树,大小为 sis_i

接下来 si1s_i-1 行,每行两个整数 u,vu,v 和一个字符 cc,表示 uu 号节点和 vv 号节点之间有一条边,边上的字母为 cc。若长出子树之前当前树的大小是 nn,则这 si1s_i-1 个点的编号分别为 n+1,n+2n+si1n+1,n+2…n+s_i-1

opt=3\text{opt}=3,则是一组询问,后面输入一个字符串 SS,询问字符串 SS 在当前 trie 中的出现次数。

输出格式

对于每个 opt=1\text{opt}=1opt=3\text{opt}=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\texttt{a},\texttt{b},\texttt{ab}

第二个询问,本质不同的子串是 $\texttt{a},\texttt{b},\texttt{c},\texttt{ab},\texttt{ac},\texttt{bb},\texttt{abb}$。

第三个询问,ab\texttt{ab} 出现次数是 22

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

opt=1\text{opt}=1opt=3\text{opt}=3 时对原树不做修改,只是询问。

每次 opt=2\text{opt}=2,会增加 si1s_i-1个节点,因为有一个节点是原树上作为新树的根出现的。

数据规模与约定

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

对于全部数据,保证从始至终每条边上的字符均为小写字母 a\texttt ab\texttt bc\texttt c

nn 是最终树的大小,n,m105n,m\le10^5sis_i 不超过当前树的大小。

题目来源

By Loi_DQS