序列 (trie)

本题使用文件输入输出，请在程序开头加入：

freopen("trie.in", "r", stdin);
freopen("trie.out", "w", stdout);

题目描述

Y 同学获得了一棵包含 $N+1$ 个节点的树，节点编号为 $0 \sim N$，其中 $0$ 号节点为根节点。这棵树共有 $N$ 条边，第 $i$ 条边连接节点 $a_i$ 与节点 $i$。

Y 同学需要为每条边分配一个低写英文字母（'a' 到 'z'），使得该树满足 字典树（Trie） 的性质：对于任意一个节点，其所有出边上的字符互不相同。

在字典树中，每个节点 $x$ 都代表一个字符串 $s(x)$。定义如下：

• 根节点 $0$ 代表空串。
• 若节点 $u$ 是节点 $v$ 的父节点，且连接 $u, v$ 的边上的字符为 $c$，则 $s(v) = s(u) + c$（其中 $+$ 表示字符串拼接）。
• 在合法的字典树中，每个节点代表的字符串是互不相同的。

给定树中 $M$ 个关键节点的集合 $K = \{k_1, k_2, \dots, k_m\}$。题目保证树中所有的叶子节点都属于 $K$。

令序列 $A = \{s(k_1), s(k_2), \dots, s(k_m)\}$。将 $A$ 中的所有字符串按字典序从小到大排序，得到字符串序列 $B = \{w_1, w_2, \dots, w_m\}$。

Y 同学希望通过合理分配每条边上的字符，使得序列 $B$ 的字典序最小。

序列字典序的比较定义：

1. 对于两个字符串 $P$ 和 $Q$，其字典序比较方式与标准一致。
2. 对于两个长度相同的字符串序列 $F = \{f_1, f_2, \dots, f_m\}$ 和 $G = \{g_1, g_2, \dots, g_m\}$，若存在整数 $1 \le t \le m$，使得对于所有 $1 \le i < t$ 均有 $f_i = g_i$，且 $f_t$ 的字典序小于 $g_t$，则称序列 $F$ 的字典序小于序列 $G$。

若存在多种分配方案使得序列 $B$ 的字典序最小，请输出使得边权序列 $c_1 c_2 \dots c_n$ 字典序最小的方案。其中 $c_i$ 是连接 $a_i$ 与 $i$ 的边上的字符。

输入格式

从 trie.in 文件读入数据。

输入包含多组测试数据。第一行包含一个整数 $T$，表示测试数据的组数。

对于每组测试数据： 第一行包含两个整数 $N$ 和 $M$，分别表示除根以外的节点数和关键节点的数量。 第二行包含 $N$ 个整数 $a_1, a_2, \dots, a_n$，其中 $a_i$ 表示节点 $i$ 的父节点编号。保证每个节点最多有 $26$ 个子节点。 第三行包含 $M$ 个整数 $k_1, k_2, \dots, k_m$，表示关键节点的编号。保证所有叶子节点均在其中，且关键节点编号各不相同。

输出格式

输出到 trie.out 文件。

对于每组测试数据，输出一行一个长度为 $N$ 的字符串 $c_1 c_2 \dots c_n$，其中 $c_i$ 表示连接 $a_i$ 与 $i$ 的边上的字符。

样例

样例输入 #1

2
5 4
0 1 1 2 2
1 4 3 5
1 1
0
1

样例输出 #1

abaab
a

数据范围与约定

对于 $100\%$ 的数据，保证 $1 \le T \le 10^3$，$1 \le M \le N \le 2 \times 10^5$，$\sum N \le 2 \times 10^5$。保证 $0 \le a_i < i$，$1 \le k_i \le N$。

• 特殊性质 A：保证树的形态为一条链，即每个节点最多只有一个子节点。
• 特殊性质 B：保证每个节点最多只有两个子节点。

大样例

点击链接 bigdata1.in 和 bigdata1.out 下载大样例 1 的输入输出数据。

点击链接 bigdata2.in 和 bigdata2.out 下载大样例 2 的输入输出数据。

点击链接 bigdata3.in 和 bigdata3.out 下载大样例 3 的输入输出数据。

点击链接 bigdata4.in 和 bigdata4.out 下载大样例 4 的输入输出数据。