AB Tree
Contest: Codeforces Round 699 (Div. 2)
Difficulty rating: 3100
Tags: dp, greedy, trees

Kilani and Abd are neighbors for 3000 years, but then the day came and Kilani decided to move to another house. As a farewell gift, Kilani is going to challenge Abd with a problem written by their other neighbor with the same name Abd.

The problem is:

You are given a connected tree rooted at node $$$1$$$.

You should assign a character a or b to every node in the tree so that the total number of a's is equal to $$$x$$$ and the total number of b's is equal to $$$n - x$$$.

Let's define a string for each node $$$v$$$ of the tree as follows:

- if $$$v$$$ is root then the string is just one character assigned to $$$v$$$:
- otherwise, let's take a string defined for the $$$v$$$'s parent $$$p_v$$$ and add to the end of it a character assigned to $$$v$$$.

You should assign every node a character in a way that minimizes the number of distinct strings among the strings of all nodes.

Input format:
The first line contains two integers $$$n$$$ and $$$x$$$ ($$$1 \leq n \leq 10^5$$$; $$$0 \leq x \leq n$$$) — the number of vertices in the tree the number of a's.

The second line contains $$$n - 1$$$ integers $$$p_2, p_3, \dots, p_{n}$$$ ($$$1 \leq p_i \leq n$$$; $$$p_i \neq i$$$), where $$$p_i$$$ is the parent of node $$$i$$$.

It is guaranteed that the input describes a connected tree.

Output format:
In the first line, print the minimum possible total number of distinct strings.

In the second line, print $$$n$$$ characters, where all characters are either a or b and the $$$i$$$-th character is the character assigned to the $$$i$$$-th node.

Make sure that the total number of a's is equal to $$$x$$$ and the total number of b's is equal to $$$n - x$$$.

If there is more than one answer you can print any of them.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
The tree from the sample is shown below:

The tree after assigning characters to every node (according to the output) is the following:

Strings for all nodes are the following:

- string of node $$$1$$$ is: a
- string of node $$$2$$$ is: aa
- string of node $$$3$$$ is: aab
- string of node $$$4$$$ is: aab
- string of node $$$5$$$ is: aabb
- string of node $$$6$$$ is: aabb
- string of node $$$7$$$ is: aabb
- string of node $$$8$$$ is: aabb
- string of node $$$9$$$ is: aa

The set of unique strings is $$$\{\text{a}, \text{aa}, \text{aab}, \text{aabb}\}$$$, so the number of distinct strings is $$$4$$$.

Example input:
9 3
1 2 2 4 4 4 3 1

Example output:
4
aabbbbbba

Editorial:
let the diameter of the tree (the maximum distance between a root and a leaf) be $$$d$$$, then the answer couldn't be less than $$$d+1$$$ because you will add strings of all lengths between $$$1$$$ and $$$d+1$$$.
In order to have the answer $$$d+1$$$, you need all strings with the same length to be equal, so all nodes on the same level must have the same character. Let's define an array $$$a$$$ of size $$$d+1$$$, such that $$$a_i$$$ = (number of nodes at level $$$i$$$). So if the answer is $$$d+1$$$ there must exist a subset from $$$a$$$ with sum $$$x$$$, so we assign character a to all the nodes with a level belongs to that subset, and character b to all other nodes.
To check if there is a subset with sum $$$x$$$ we can use dynamic programming, the complexity of this solution is $$$O(x \cdot (d+1))$$$, which is in worst case $$$O(n^{2})$$$.
But since the sum of array $$$a$$$ is equal to $$$n$$$, the number of unique values in $$$a$$$ will be at most $$$\sqrt{n}$$$, so lets have an array of size at most $$$\sqrt{n}$$$ having every value with it's frequency. Now let $$$dp[i][j]$$$ be true if it is possible to find a subset with sum $$$j$$$ in the suffix $$$i$$$. So to check if $$$dp[i][j]$$$ is true or not we need to check $$$dp[i+1][j - val[i]], dp[i+1][j - 2 \cdot val[i]] ... , dp[i+1][j - freq[i] \cdot val[i]]$$$, in another way we need to find a value $$$k$$$ such that $$$dp[i+1][j - k \cdot val[i]]$$$ is true and $$$(k \leq freq[i])$$$, so for every $$$j$$$ let's find the minimum possible $$$k$$$, if $$$dp[i + 1][j]$$$ is true then $$$k_j$$$ will be equal to $$$0$$$, otherwise it is equal to $$$k_{j - val[i]} + 1$$$.
So this way we can check if the answer is $$$d+1$$$ in $$$O(n \cdot \sqrt{n})$$$.
Now if the answer is not $$$d+1$$$, then it is $$$d+2$$$. To find the answer let's start from level $$$0$$$ to level $$$d$$$, when you are at level $$$i$$$ let the number of remaining nodes be $$$m$$$ (the number of nodes with depth greater than or equal to $$$i$$$) and you have $$$y$$$ remaining a's you can still use.
If $$$a_i$$$ is not greater than $$$y$$$ or not greater than $$$m-y$$$, you can assign all nodes on the current level with the same character and move on to the next level.
If not then you will have to use the two characters on the current level so you are going to add at least one more string on the answer. If you have two nodes on the same level having the same character but the nodes have different prefixes, then the strings will not be considered equal, so to guarantee not adding more than one string to the answer later on, you should make sure to assign the same character to all non-leaf nodes on the current level.
Now if we have $$$l$$$ non-leaf nodes then $$$l$$$ must be less than or equal to $$$\frac{m}{2}$$$, because every non-leaf node should have at least one more node in it's sub tree, and we know that for any value $$$y$$$ ($$$\frac{m}{2} \leq max(y , m - y)$$$), so it is possible to assign the same character to all non-leaf nodes, after assigning all non-leaf nodes with the same character make sure to finish all the remaining copies of this character on the current level so you guarantee on the next levels all nodes will be the same.
This way only one string will be added on the current level so the answer will be $$$d+2$$$.
Total complexity is $$$O(n \cdot \sqrt{n})$$$