CF1623E.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{ \lt empty string \gt }, & \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$.

给定一棵包含 $n$ 个节点的二叉树。树中节点编号为 $1$ 到 $n$，根节点为节点 $1$。每个节点可以没有子节点、仅有一个左子节点、仅有一个右子节点，或同时具有左右两个子节点。为方便起见，记节点 $u$ 的左子节点和右子节点分别为 $l_u$ 和 $r_u$；若 $u$ 无左子节点，则令 $l_u = 0$；若 $u$ 无右子节点，则令 $r_u = 0$。

每个节点带有一个字符串标签，初始时为单个字符 $c_u$。我们定义该二叉树的字符串表示为所有节点按中序遍历顺序的标签拼接结果。形式化地，令 $f(u)$ 表示以节点 $u$ 为根的子树的字符串表示。$f(u)$ 定义如下：

$$f(u) = \begin{cases} \texttt{<empty string>}, & \text{if }u = 0; \\ f(l_u) + c_u + f(r_u) & \text{otherwise}, \end{cases}$$

其中 $+$ 表示字符串拼接操作。

因此，整棵树的字符串表示即为 $f(1)$。

对于每个节点，我们至多可将其标签复制一次，即把 $c_u$ 替换为 $c_u + c_u$（即自身拼接），但前提是：该节点是整棵树的根节点，或者其父节点的标签也已被复制。

现给定该树及一个整数 $k$。若我们最多可对 $k$ 个节点执行上述复制操作，那么该树可能得到的字典序最小的字符串表示是什么？

字符串 $a$ 字典序小于字符串 $b$，当且仅当满足以下任一条件：

• $a$ 是 $b$ 的真前缀（即 $a$ 是 $b$ 的前缀，但 $a \ne b$）；
• 在 $a$ 与 $b$ 首次出现差异的位置上，$a$ 中的字符在字母表中位于 $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$.

第一行包含两个整数 $n$ 和 $k$（$1 \le k \le n \le 2 \cdot 10^5$）。

第二行包含一个长度为 $n$ 的字符串 $c$，由小写英文字母组成，其中 $c_i$ 表示节点 $i$ 的初始标签（$1 \le i \le n$）。注意：所给字符串 $c$ 并非该树的初始字符串表示。

接下来的 $n$ 行中，第 $i$ 行包含两个整数 $l_i$ 和 $r_i$（$0 \le l_i, r_i \le n$）。若节点 $i$ 无左子节点，则 $l_i = 0$；若节点 $i$ 无右子节点，则 $r_i = 0$。

保证所给输入构成一棵以节点 $1$ 为根的二叉树。

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

输出一行，包含在至多 $k$ 个节点的标签被重复的情况下，字典序最小的树的字符串表示。

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" :(.

下方图片展示了示例中的树结构。每个节点中的数字表示节点编号，下标字母表示该节点的标签。右侧为该树的字符串表示形式，其中每个字母的颜色与其对应节点的颜色相同。

以下是第一个示例对应的树。此处我们复制了节点 $1$ 和节点 $3$ 的标签。我们不应复制节点 $2$ 的标签，因为那样会得到字符串 "bbaaab"，其字典序大于 "baaaab"。

在第二个示例中，我们可以复制节点 $1$ 和节点 $2$ 的标签。注意：仅复制根节点的标签将导致结果比初始字符串更差。

在第三个示例中，我们完全不应复制任何字符。尽管我们可能希望复制节点 $3$ 的标签，但一旦复制它，就不得不同时复制节点 $2$ 的标签，从而导致更差的结果。

无法从初始字符串表示为 "darkcyan" 的树中生成字符串 "darkkcyan" :(.