Middle Duplication

题意翻译

你有一个包含 $n$ 个节点的二叉树，节点编号为 $1\sim n$，其中根节点的编号为 $1$。每个节点上面的儿子的拥有情况有四种：没有儿子，只有左儿子，只有右儿子和同时拥有左儿子和右儿子。为了方便，我们定义 $l_u,r_u$ 分别为节点 $u$ 的左儿子和右儿子，特别地，$l_u=0$ 时表示节点 $u$ 没有左儿子，$r_u=0$ 时表示节点 $u$ 没有右儿子。 每个节点上都有一个字符串，最初节点 $u$ 上面的字符串是 $c_u$，其仅包含一个字符。让我们定义 $f(u)$ 为节点 $u$ 的子树的字符串表示。下面展示了计算 $f(u)$ 的公式，其中 $+$ 在此处定义为**字符串拼接操作**，下同。 $$f(u)=\begin{cases}<\text{空字符串}>&u=0\\f(l_u)+c_u+f(r_u)&\text{otherwise}\end{cases}$$ 定义这个二叉树的字符串表示为其根节点的字符串表示，即 $f(1)$。 你喜欢字典序尽可能小的字符串，所以你现在可以对二叉树上的所有节点进行**至多一次**复制操作。对于节点 $u$，其进行复制操作之后，它的字符串由 $c_u$ 变为 $c_u+c_u$。$u$ 可以复制，当且仅当 $u$ 是根或者 $u$ 的父节点被复制。你想知道在至多有 $k$ 个节点进行复制操作之后，该二叉树字典序最小的字符串表示。 我们定义字符串 $a$ 的字典序小于字符串 $b$，当且仅当： - $a$ 是 $b$ 的前缀时，$a\neq b$。 - $a$ 不是 $b$ 的前缀时，存在一个位置 $p$，使得 $\forall i\in[1,p)$，$a_i=b_i$，且 $a_p<b_p$。其中我们称字符 $c<c'$，当且仅当字符 $c$ 的 ASCII 码小于字符 $c'$ 的 ASCII 码。 数据范围： - $1\leqslant k\leqslant n\leqslant 2\times 10^5$。 - $0\leqslant l_i,r_i\leqslant n$。 Translated by Eason_AC 2021.12.29

题目描述

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.

输入输出样例

输入样例 #1

4 3
abab
2 3
0 0
0 4
0 0

输出样例 #1

baaaab

输入样例 #2

8 2
kadracyn
2 5
3 4
0 0
0 0
6 8
0 7
0 0
0 0

输出样例 #2

daarkkcyan

输入样例 #3

8 3
kdaracyn
2 5
0 3
0 4
0 0
6 8
0 7
0 0
0 0

输出样例 #3

darkcyan

说明

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