← 返回题目列表

Codeforces · 1623/E

E. 中间重复

中文机器翻译题面 查看原题

给出了 $$$n$$$ 个节点的二叉树。树的节点从 $$$1$$$ 到 $$$n$$$ 编号,根是节点 $$$1$$$。每个节点可以没有子节点、只有一个左子节点、只有一个右子节点或两个子节点。为了方便起见,我们将 $$$l_u$$$ 和 $$$r_u$$$ 分别表示为节点 $$$u$$$ 的左子节点和右子节点,如果 $$$u$$$ 没有左子节点,则 $$$l_u = 0$$$;如果 $$$u$$$ 没有右子节点,则 $$$r_u = 0$$$。

每个节点都有一个字符串标签,最初是单个字符$$$c_u$$$。让我们将二叉树的字符串表示形式定义为按顺序排列的节点标签的串联。形式上,令 $$$f(u)$$$ 为以节点 $$$u$$$ 为根的树的字符串表示形式。 $$$f(u)$$$ 定义如下: $$$$$$ f(u) = \begin{cases} \texttt{<空字符串>}, & \text{if }u = 0; \\ f(l_u) + c_u + f(r_u) & \text{otherwise}, \end{cases} $$$$$$ 其中 $$$+$$$ 表示字符串连接操作。

这样,树的字符串表示形式就是 $$$f(1)$$$。

对于每个节点,我们最多可以复制其标签一次,即用 $$$c_u + c_u$$$ 分配 $$$c_u$$$,但前提是 $$$u$$$ 是树的根,或者其父节点也有重复的标签。

给你一棵树和一个整数$$$k$$$。如果我们最多可以复制 $$$k$$$ 节点的标签,那么按字典顺序排列的树的最小字符串表示是什么?

当且仅当满足以下条件之一时,字符串 $$$a$$$ 按字典顺序小于字符串 $$$b$$$:

- $$$a$$$ 是 $$$b$$$ 的前缀,但 $$$a \ne b$$$;
- 在 $$$a$$$ 和 $$$b$$$ 不同的第一个位置,字符串 $$$a$$$ 在字母表中的某个字母比 $$$b$$$ 中的相应字母更早出现。

输入

第一行包含两个整数 $$$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$$$。

输出

如果至多 $$$k$$$ 节点的标签重复,则打印一行,其中包含树的字典顺序最小的字符串表示形式。

示例

输入 #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

注意

下图展示了示例的树。每个节点中的数字是节点号,下标字母是其标签。右侧是树的字符串表示形式,每个字母与相应节点具有相同的颜色。

这是第一个示例的树。这里我们复制了节点 $$$1$$$ 和 $$$3$$$ 的标签。我们不应该重复节点 $$$2$$$ 的标签,因为它会给我们字符串“bbaaab”,它按字典顺序大于“baaaab”。

在第二个示例中,我们可以复制节点 $$$1$$$ 和 $$$2$$$ 的标签。请注意,仅复制根的标签会产生比初始字符串更糟糕的结果。

在第三个示例中,我们根本不应该重复任何字符。即使我们想要复制节点 $$$3$$$ 的标签,通过复制它,我们也必须复制节点 $$$2$$$ 的标签,这会产生更糟糕的结果。

无法从初始字符串表示“darkcyan”的树中生成字符串“darkkcyan”:(。