Middle Duplication
Contest: Codeforces Round 763 (Div. 2)
Difficulty rating: 2500
Tags: data structures, dfs and similar, greedy, strings, trees

A binary tree of $$$n$$$ nodes is given. Nodes of the tree are numbered from $$$1$$$ to $$$n$$$ and the root is the node $$$1$$$. Each node can have no child, only one left child, only one right child, or both children. For convenience, let's denote $$$l_u$$$ and $$$r_u$$$ as the left and the right child of the node $$$u$$$ respectively, $$$l_u = 0$$$ if $$$u$$$ does not have the left child, and $$$r_u = 0$$$ if the node $$$u$$$ does not have the right child.

Each node has a string label, initially is a single character $$$c_u$$$. Let's define the string representation of the binary tree as the concatenation of the labels of the nodes in the in-order. Formally, let $$$f(u)$$$ be the string representation of the tree rooted at the node $$$u$$$. $$$f(u)$$$ is defined as follows: $$$$$$ f(u) = \begin{cases} \texttt{<empty string>}, & \text{if }u = 0; \\ f(l_u) + c_u + f(r_u) & \text{otherwise}, \end{cases} $$$$$$ where $$$+$$$ denotes the string concatenation operation.

This way, the string representation of the tree is $$$f(1)$$$.

For each node, we can duplicate its label at most once, that is, assign $$$c_u$$$ with $$$c_u + c_u$$$, but only if $$$u$$$ is the root of the tree, or if its parent also has its label duplicated.

You are given the tree and an integer $$$k$$$. What is the lexicographically smallest string representation of the tree, if we can duplicate labels of at most $$$k$$$ nodes?

A string $$$a$$$ is lexicographically smaller than a string $$$b$$$ if and only if one of the following holds:

- $$$a$$$ is a prefix of $$$b$$$, but $$$a \ne b$$$;
- in the first position where $$$a$$$ and $$$b$$$ differ, the string $$$a$$$ has a letter that appears earlier in the alphabet than the corresponding letter in $$$b$$$.

Input format:
The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le k \le n \le 2 \cdot 10^5$$$).

The second line contains a string $$$c$$$ of $$$n$$$ lower-case English letters, where $$$c_i$$$ is the initial label of the node $$$i$$$ for $$$1 \le i \le n$$$. Note that the given string $$$c$$$ is not the initial string representation of the tree.

The $$$i$$$-th of the next $$$n$$$ lines contains two integers $$$l_i$$$ and $$$r_i$$$ ($$$0 \le l_i, r_i \le n$$$). If the node $$$i$$$ does not have the left child, $$$l_i = 0$$$, and if the node $$$i$$$ does not have the right child, $$$r_i = 0$$$.

It is guaranteed that the given input forms a binary tree, rooted at $$$1$$$.

Output format:
Print a single line, containing the lexicographically smallest string representation of the tree if at most $$$k$$$ nodes have their labels duplicated.

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

Note:
The images below present the tree for the examples. The number in each node is the node number, while the subscripted letter is its label. To the right is the string representation of the tree, with each letter having the same color as the corresponding node.

Here is the tree for the first example. Here we duplicated the labels of nodes $$$1$$$ and $$$3$$$. We should not duplicate the label of node $$$2$$$ because it would give us the string "bbaaab", which is lexicographically greater than "baaaab".

In the second example, we can duplicate the labels of nodes $$$1$$$ and $$$2$$$. Note that only duplicating the label of the root will produce a worse result than the initial string.

In the third example, we should not duplicate any character at all. Even though we would want to duplicate the label of the node $$$3$$$, by duplicating it we must also duplicate the label of the node $$$2$$$, which produces a worse result.

There is no way to produce string "darkkcyan" from a tree with the initial string representation "darkcyan" :(.

Example input:
4 3
abab
2 3
0 0
0 4
0 0

Example output:
baaaab

Example input:
8 2
kadracyn
2 5
3 4
0 0
0 0
6 8
0 7
0 0
0 0

Example output:
daarkkcyan

Editorial:
Firstly, we need to determine if a label should be duplicated at all. For example, in the string "bac", the characters 'b' and 'c' should never be duplicated, since duplicating them always make the result worse ("bbac" and "bacc" are both lexicographically greater than "bac"). This is because, next to the character 'b' is 'a', and 'a' is smaller than 'b'. For the case of 'c', after it there is no more characters, thus we should not duplicate it as well. Let's call a node good if duplicating its label will make the result better (lexicographically smaller). To find good nodes, we can find the initial string representation of the tree using DFS. A node is good if the next different character in the string representation must exist and is smaller than the label of the node.
After finding the good nodes, let's find the first label that we should duplicate. This label must be from a good label and must lie as close to the start of the string as possible. We can find this label, also by DFS. We still do DFS in the in-order, and the first good node having depth not exceed $$$k$$$ will be the first node to have the label duplicated. And by duplicating this node, we must duplicate the labels of its ancestors as well. Note that during the DFS process, if we don't duplicate a node, we should not go to the right sub-tree.
Let's call the cost of duplicating a node the number of its ancestors that is not duplicated before. The cost of the first duplicated node is its depth, which can be calculated while doing DFS. The cost of the other nodes can also be maintained while doing DFS as well: if a node is duplicated, the root going to the right sub-tree will have a cost of $$$1$$$.
So overall we will have the following DFS algorithm on the node $$$u$$$:
1. If $$$u = 0$$$, then we do nothing.
2. If $$$cost[u] > k$$$ , we do nothing.
3. Assign $$$cost[l[u]] \gets cost[u] + 1$$$ and do DFS on $$$l[u]$$$.
4. If $$$l[u]$$$ has it label duplicated, we duplicate the label of $$$u$$$.
5. Otherwise, if $$$u$$$ is good, we duplicate the label of $$$u$$$ as well, and decrease $$$k$$$ by $$$cost[u]$$$.
6. If $$$u$$$ is duplicated, then assign $$$cost[r[u]] \gets 1$$$, do DFS on $$$r[u]$$$.
For implementation, we can pass the variable cost together with $$$u$$$ to the DFS function, and don't need to declare a global array.
The overall time complexity of this solution is $$$O(n)$$$.