Trie
题目描述
回顾字典树的定义:
- 大小为 N 的字典树是一棵有 N 个顶点、N−1 条边的有根树,每条边标有一个字符。
- 每个顶点表示一个字符串,记顶点 x 表示的字符串为 s(x)。
- 根表示空字符串。若 u 是 v 的父亲,连接它们的边上的字符为 c,则 s(v)=s(u)+c,其中 + 表示字符串拼接。
- 所有顶点表示的字符串互不相同。
现在给出一棵有 n+1 个顶点的有根树,顶点编号为 0,1,…,n,根为 0。树上有 m 个关键顶点,第 i 个关键顶点为 ki。保证所有叶子都是关键顶点。
请给每条边标上一个小写英文字母,使这棵树成为大小为 n+1 的字典树。考虑关键顶点表示的字符串序列 A={s(k1),s(k2),…,s(km)},把它按字典序从小到大排序,得到 B={w1,w2,…,wm}。你需要使序列 B 尽可能小。
字符串 P=p1⋯px 的字典序小于字符串 Q=q1⋯qy,当且仅当以下条件之一成立:
- x<y 且对所有 1≤i≤x,均有 pi=qi;
- 存在 1≤t≤min(x,y),使得 t 前的对应字符均相同,且 pt<qt。
对两个长度同为 m 的字符串序列 F={f1,…,fm} 与 G={g1,…,gm},若存在第一个不同的位置 t,其前面的对应字符串均相同,且 ft 的字典序小于 gt,则称 F 小于 G。
输入格式
第一行一个整数 T,表示测试用例数。每个测试用例:
第一行两个整数 n,m(1≤m≤n≤2×105),表示除根以外的顶点数和关键顶点数。
第二行 n 个整数 a1,…,an(0≤ai<i),其中 ai 是顶点 i 的父亲。保证每个顶点至多有 26 个孩子。
第三行 m 个整数 k1,…,km(1≤ki≤n),表示关键顶点。所有关键顶点互不相同,且所有叶子都是关键顶点。
保证同一输入文件内所有用例的 n 之和不超过 2×105。原题未另行限制 T。
输出格式
每个测试用例输出一行长度为 n、只含小写英文字母的字符串 c1c2⋯cn,其中 ci 是连接 ai 与 i 的边上的字符。
如果存在多种标号方式使 B 最小,请输出其中 c1c2⋯cn 的字典序最小的一种。
样例输入
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}。
