A14833 | Middle Duplication

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.</p><p>This way, the string representation of the tree is $f(1)$ .</p><p>For each node, we can <span class="tex-font-style-it">duplicate</span> its label <span class="tex-font-style-bf">at most once</span>, 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.</p><p>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?</p><p>A string $a$ is lexicographically smaller than a string $b$ if and only if one of the following holds: </p><ul> <li> $a$ is a prefix of $b$ , but $a \\ne b$ ; </li><li> 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$$$.

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$ .

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