309096: CF1623E. Middle Duplication
Memory Limit:256 MB
Time Limit:1 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
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