字典树逆向

Problem Description

字典树（Trie）是像字典一样的树。如下图所示，字典树用边来代表字符，每个节点到它的所有子节点的边上的字符互不相同，而从根节点到树上某一节点的路径就代表一个字符串，例如 $1\rightarrow4\rightarrow8\rightarrow12$ 表示字符串 “$\texttt{caa}$”。 注意，本题中字符集为所有正整数，并非 26 个小写字母。 有 $n$ 个非空的字符串 $S_1,S_2,\dots,S_n$ 被构造成了一棵字典树 $\mathcal{T}$，它包含 $m$ 个节点，其中 1 号节点为根节点，剩下节点的编号被打乱了。现在给定 $\mathcal{T}$，请还原这 $n$ 个非空的字符串。 若有多个可行方案，请输出 $n$ 最小的方案；若在此基础上还有多个可行方案，请输出 $[S_1, S_2, \dots, S_n]$ 字典序最小的方案。 字符串序列 $[A_1, A_2, \dots, A_n]$ 的字典序小于字符串序列 $[B_1, B_2, \dots, B_n]$ 当且仅当存在某个 $k$（$1\leq k\leq n$）满足字符串 $A_i=B_i$（$1\leq i < k$）且字符串 $A_k < B_k$。请注意，这里的字符串比较也为字典序比较。 字符串 $C$ 的字典序小于字符串 $D$ 当且仅当 $C$ 是 $D$ 的前缀或者存在某个 $k$（$1\leq k\leq \min(|C|,|D|)$）满足 $C[i]=D[i]$（$1\leq i < k$)且 $C[k] < D[k]$，其中 $C[k]$ 表示字符串 $C$ 的第 $k$ 个字符。

Input

第一行包含一个正整数 $T$（$1\leq T\leq 500$），表示测试数据的组数。 每组数据第一行包含一个正整数 $m$（$2\leq m\leq 200\,000$），表示字典树的节点数。 第二行包含 $m-1$ 个正整数 $f_2,f_3,\dots,f_m$（$1\leq f_i < i$），依次表示每个节点的父节点编号。 输入数据保证 $\sum m\leq 2\,000\,000$。

Output

每组数据第一行输出一个正整数 $n$，表示字符串的数量。 接下来 $n$ 行，第 $i$ 行的输出代表字符串 $S_i$。由于字符串可能很长，请输出它的哈希值 $\left(\sum_{j=1}^{|S_i|}998\,244\,353^{|S_i|-j}\cdot S_i[j]\right)\bmod 2^{64}$。

Sample Input

4
2
1
3
1 1
4
1 2 1
6
1 2 1 4 5

Sample Output

1
1
2
1
2
2
1
1996488707
2
998244354
1992983577591021572

Hint

样例一的方案为：$S_1=[1]$。 样例二的方案为：$S_1=[1]$，$S_2=[2]$。 样例三的方案为：$S_1=[1]$，$S_2=[2,1]$。 样例四的方案为：$S_1=[1,1]$，$S_2=[2,1,1]$。

Source

2025“钉耙编程”中国大学生算法设计暑期联赛（7）