CF1481F AB Tree

Kilani 和 Abd 已经做了 3000 年的邻居，但终于有一天，Kilani 决定搬到另一个房子。作为告别礼物，Kilani 决定用他们另一位同名邻居 Abd 出的一道题来考考 Abd。 你得到了一棵以 $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$ 的字符串为：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$。 由 ChatGPT 4.1 翻译