#P18706. Trie

Trie

Trie

题目描述

回顾字典树的定义:

  • 大小为 NN 的字典树是一棵有 NN 个顶点、N−1N-1 条边的有根树,每条边标有一个字符。
  • 每个顶点表示一个字符串,记顶点 xx 表示的字符串为 s(x)s(x)。
  • 根表示空字符串。若 uu 是 vv 的父亲,连接它们的边上的字符为 cc,则 s(v)=s(u)+cs(v)=s(u)+c,其中 ++ 表示字符串拼接。
  • 所有顶点表示的字符串互不相同。

现在给出一棵有 n+1n+1 个顶点的有根树,顶点编号为 0,1,…,n0,1,\ldots,n,根为 00。树上有 mm 个关键顶点,第 ii 个关键顶点为 kik_i。保证所有叶子都是关键顶点。

请给每条边标上一个小写英文字母,使这棵树成为大小为 n+1n+1 的字典树。考虑关键顶点表示的字符串序列 A={s(k1),s(k2),…,s(km)}A=\{s(k_1),s(k_2),\ldots,s(k_m)\},把它按字典序从小到大排序,得到 B={w1,w2,…,wm}B=\{w_1,w_2,\ldots,w_m\}。你需要使序列 BB 尽可能小。

字符串 P=p1⋯pxP=p_1\cdots p_x 的字典序小于字符串 Q=q1⋯qyQ=q_1\cdots q_y,当且仅当以下条件之一成立:

  • x<yx<y 且对所有 1≤i≤x1\le i\le x,均有 pi=qip_i=q_i;
  • 存在 1≤t≤min⁡(x,y)1\le t\le\min(x,y),使得 tt 前的对应字符均相同,且 pt<qtp_t<q_t。

对两个长度同为 mm 的字符串序列 F={f1,…,fm}F=\{f_1,\ldots,f_m\} 与 G={g1,…,gm}G=\{g_1,\ldots,g_m\},若存在第一个不同的位置 tt,其前面的对应字符串均相同,且 ftf_t 的字典序小于 gtg_t,则称 FF 小于 GG。

输入格式

第一行一个整数 TT,表示测试用例数。每个测试用例:

第一行两个整数 n,mn,m(1≤m≤n≤2×1051\le m\le n\le2\times10^5),表示除根以外的顶点数和关键顶点数。

第二行 nn 个整数 a1,…,ana_1,\ldots,a_n(0≤ai<i0\le a_i<i),其中 aia_i 是顶点 ii 的父亲。保证每个顶点至多有 26 个孩子。

第三行 mm 个整数 k1,…,kmk_1,\ldots,k_m(1≤ki≤n1\le k_i\le n),表示关键顶点。所有关键顶点互不相同,且所有叶子都是关键顶点。

保证同一输入文件内所有用例的 nn 之和不超过 2×1052\times10^5。原题未另行限制 TT。

输出格式

每个测试用例输出一行长度为 nn、只含小写英文字母的字符串 c1c2⋯cnc_1c_2\cdots c_n,其中 cic_i 是连接 aia_i 与 ii 的边上的字符。

如果存在多种标号方式使 BB 最小,请输出其中 c1c2⋯cnc_1c_2\cdots c_n 的字典序最小的一种。

样例输入

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

样例输出

abaab
a

样例说明

第一个用例的答案如下图。顶点 1 表示 a,顶点 4 表示 aba,顶点 3 表示 aa,顶点 5 表示 abb,因此 B={a,aa,aba,abb}B=\{\text{a},\text{aa},\text{aba},\text{abb}\}。

原题第一个样例字典树