3644. 后缀 Trie

单点时限: 3.0 sec

内存限制: 512 MB

Trie 是一种常见的数据结构。不知道 Trie 为何物的,请自行网搜。

若将一个长度为 $n$ 的字符串的所有后缀(总共 $n$ 个)插入一个 Trie 中,则称该 Trie 为字符串的后缀 Trie。

现以有根树的形式给出一个后缀 Trie,试问该树是否为一合法的后缀 Trie。如果是,求出原字符串。

输入格式

第一行一个整数 $T$,表示有 $T$ ($1 \le T \le 333~333$) 组测试数据。

每组测试数据有四行。第一行一个整数 $n$ ($2 \le n \le 2 \cdot 10^5$),表示树的节点个数。节点从 $1$ 到 $n$ 编号。

第二行 $n-1$ 个整数 $p_2, p_3, \ldots, p_n$ ($1 \le p_i \le i - 1$),分别表示 $2,3,\ldots,n$ 的父亲节点的编号。由于节点 1 是根, 它没有父亲。

第三行是一个长度 $n-1$ 的字符串 $s_2s_3 \ldots s_n$,依次表示节点 $2,3,\ldots,n$ 到父亲节点的边上的字符。$s_i$ 是英文小写字母。

第四行是一个长度为 $n-1$ 的 01 字符串 $a_2a_3 \ldots a_n$,依次表示节点 $2,3,\ldots,n$ 是否是终态。 1 表示是, 0 表示不是。由于字符串的后缀不可能是空串,所以显然节点 1 不是终态。

另外,保证 $T$ 组测试数据中的 $n$ 的和不超过 $2 \cdot 10^6$,且不存在两个节点 $u$, $v$ 满足 $p_u = p_v$ 且 $s_u = s_v$。

本题数据量较大,请注意输入输出上的优化。

输出格式

对于每组测试数据,如果是合法的后缀 Trie,输出一行表示原字符串;如果不是,输出 Illegal

样例

Input
2
11
1 1 1 2 2 4 6 6 6 7
taioenadnn
0111011111
16
1 1 1 2 3 4 5 6 7 8 9 10 11 12 15
abnnaaannnaaana
100001100001101
Output
Illegal
banana

提示

下图对应样例 1 中的树。

下图对应样例 2 中的树。

18 人解决,32 人已尝试。

22 份提交通过,共有 185 份提交。

6.1 EMB 奖励。

创建: 2 年,4 月前.

修改: 1 年,12 月前.

最后提交: 9 月,4 周前.

来源: EOJ Monthly 2018.10

题目标签