#P3906. Trie

    ID: 3108 传统题 1000ms 256MiB 尝试: 13 已通过: 4 难度: 8 上传者: 标签>CF2500提高+/省选-AC 自动机子树转区间DFS 序排序差分树状数组LCA树上倍增容斥原理2014Asia

Trie

题目描述

给定一棵由小写英文字母标记边的 Trie,根为 11。设 SiS_i 是从根到节点 ii 的路径上各边字母按顺序连接得到的字符串。根对应空串,空串是所有字符串的后缀。

一个特征由一个节点集合 PP 定义。如果存在 j∈Pj\in P,使 SjS_j 是 SiS_i 的后缀,就说 SiS_i 具有该特征。对同一次添加,一个字符串即使匹配多个节点也只获得一个特征。设 DiD_i 为至今已经添加且 SiS_i 具有的特征个数,初始为 00。

有两种操作。

  1. 给定集合 PP,添加一个由 PP 定义的特征。每次操作都是一次新的添加。
  2. 给定集合 PP。令 $f(P)=\{i\mid \text{存在 }j\in P\text{ 使 }S_i\text{ 是 }S_j\text{ 的后缀}\}$,求 ∑i∈f(P)Di\sum_{i\in f(P)}D_i。一个节点即使是多个字符串的后缀,也只计一次。

输入格式

第一行一个整数 TT(1≤T≤51\le T\le5),表示数据组数。

每组第一行一个整数 nn(1≤n≤1051\le n\le10^5)。接下来依次给出节点 i=2,…,ni=2,\dots,n 的父节点 uu 和连接它们的小写字母 cc,满足 1≤u<i1\le u<i。同一父节点到各子节点的字母互不相同。

下一行一个整数 mm(m≤105m\le10^5),表示操作数。接下来 mm 行,每行先给出操作类型(1 或 2)与集合大小 kk,再给出 kk 个互不相同的节点编号。每组所有集合的大小之和不超过 5⋅1055\cdot10^5。

输出格式

对每组数据的每个 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

2014 ICPC 亚洲鞍山赛站原题存档