← 返回题目列表

Codeforces · 1481/F

F. AB 树

中文机器翻译题面 查看原题

Kilani 和 Abd 是 3000 年的邻居,但有一天,Kilani 决定搬到另一所房子。作为告别礼物,基拉尼将用另一个同名阿卜杜勒邻居写的问题向阿卜杜勒挑战。

问题是:

给你一个以节点 $$$1$$$ 为根的连通树。

您应该为树中的每个节点分配一个字符 a 或 b,以便 a 的总数等于 $$$x$$$,b 的总数等于 $$$n - x$$$。

让我们为树的每个节点 $$$v$$$ 定义一个字符串,如下所示:

- 如果 $$$v$$$ 是根,则该字符串只是分配给 $$$v$$$ 的一个字符:
- 否则,我们采用为 $$$v$$$ 的父级 $$$p_v$$$ 定义的字符串,并在其末尾添加一个分配给 $$$v$$$ 的字符。

您应该以最小化所有节点字符串中不同字符串数量的方式为每个节点分配一个字符。

输入

第一行包含两个整数 $$$n$$$ 和 $$$x$$$ ($$$1 \leq n \leq 10^5$$$; $$$0 \leq x \leq n$$$) - 树中顶点的数量 a 的数量。

第二行包含 $$$n - 1$$$ 整数 $$$p_2, p_3, \dots, p_{n}$$$ ($$$1 \leq p_i \leq n$$$; $$$p_i \neq i$$$),其中 $$$p_i$$$ 是节点 $$$i$$$ 的父节点。

保证输入描述的是连通树。

输出

在第一行中,打印不同字符串的最小可能总数。

在第二行中,打印 $$$n$$$ 个字符,其中所有字符都是 a 或 b,第 $$$i$$$ 个字符是分配给第 $$$i$$$ 个节点的字符。

确保 a 的总数等于 $$$x$$$,b 的总数等于 $$$n - x$$$。

如果有多个答案,您可以打印其中任何一个。

示例

输入 #1

9 3
1 2 2 4 4 4 3 1

输出 #1

4
aabbbbbba

注意

示例中的树如下所示:

为每个节点分配字符后的树(根据输出)如下:

所有节点的字符串如下:

- 节点 $$$1$$$ 的字符串是:a
- 节点 $$$2$$$ 的字符串是:aa
- 节点 $$$3$$$ 的字符串是:aab
- 节点 $$$4$$$ 的字符串是:aab
- 节点 $$$5$$$ 的字符串是:aabb
- 节点 $$$6$$$ 的字符串是:aabb
- 节点 $$$7$$$ 的字符串是:aabb
- 节点 $$$8$$$ 的字符串是:aabb
- 节点 $$$9$$$ 的字符串是:aa

唯一字符串的集合为 $$$\{\text{a}、\text{aa}、\text{aab}、\text{aabb}\}$$$,因此不同字符串的数量为 $$$4$$$。