#P3906. Trie
Trie
题目描述
给定一棵由小写英文字母标记边的 Trie,根为 。设 是从根到节点 的路径上各边字母按顺序连接得到的字符串。根对应空串,空串是所有字符串的后缀。
一个特征由一个节点集合 定义。如果存在 ,使 是 的后缀,就说 具有该特征。对同一次添加,一个字符串即使匹配多个节点也只获得一个特征。设 为至今已经添加且 具有的特征个数,初始为 。
有两种操作。
- 给定集合 ,添加一个由 定义的特征。每次操作都是一次新的添加。
- 给定集合 。令 $f(P)=\{i\mid \text{存在 }j\in P\text{ 使 }S_i\text{ 是 }S_j\text{ 的后缀}\}$,求 。一个节点即使是多个字符串的后缀,也只计一次。
输入格式
第一行一个整数 (),表示数据组数。
每组第一行一个整数 ()。接下来依次给出节点 的父节点 和连接它们的小写字母 ,满足 。同一父节点到各子节点的字母互不相同。
下一行一个整数 (),表示操作数。接下来 行,每行先给出操作类型(1 或 2)与集合大小 ,再给出 个互不相同的节点编号。每组所有集合的大小之和不超过 。
输出格式
对每组数据的每个 2 类操作输出一行一个整数,表示答案。
样例
1
6
1 a
1 b
1 c
3 a
3 b
5
1 2 3 4
2 2 5 6
1 2 2 3
2 2 4 5
2 1 6
2
3
4