E. Дублирование среднего
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дано бинарное дерево из $$$n$$$ вершин. Вершины дерева пронумерованы от $$$1$$$ до $$$n$$$, корень дерева имеет номер $$$1$$$. Каждая вершина может не иметь детей, иметь только правого или только левого ребенка, или иметь двух детей. Для удобства обозначим за $$$l_u$$$ и $$$r_u$$$ левого и правого ребенка вершины $$$u$$$ соответственно, при этом $$$l_u = 0$$$, если у $$$u$$$ нет левого ребенка, и $$$r_u = 0$$$, если у $$$u$$$ нет правого ребенка.

В каждой вершине дерева записана некоторая строка, изначально состоящая из одного символа $$$c_u$$$. Определим строковое представление дерева как конкатенацию всех строк, записанных в вершинах, в порядке центрированного обхода. Формально, пусть $$$f(u)$$$ — строковое представление поддерева с корнем в вершине $$$u$$$. $$$f(u)$$$ определена так: $$$$$$ f(u) = \begin{cases} \texttt{<пустая строка>,} & \text{если }u = 0; \\ f(l_u) + c_u + f(r_u) & \text{иначе}, \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$$$).

Вторая строка содержит строку $$$c$$$, состоящую из $$$n$$$ маленьких букв латинского алфавита, где $$$c_i$$$ — строка, записанная в вершине $$$i$$$ изначально, $$$1 \le i \le n$$$. Обратите внимание, что данная строка $$$c$$$ не является начальным строковым представлением дерева.

$$$i$$$-я из следующих $$$n$$$ строк содержит два целых числа $$$l_i$$$ и $$$r_i$$$ ($$$0 \le l_i, r_i \le n$$$). Если у $$$i$$$-й вершины нет левого ребенка, $$$l_i = 0$$$, и если у $$$i$$$-й вершины нет правого ребенка, $$$r_i = 0$$$.

Гарантируется, что данные значения описывают корректное бинарное дерево с корнем в $$$1$$$.

Выходные данные

Выведите одну строку, содержащую лексикографически минимальное строковое представление, которое может иметь дерево после не более чем в $$$k$$$ вершинах строка будет продублирована.

Примеры
Входные данные
4 3
abab
2 3
0 0
0 4
0 0
Выходные данные
baaaab
Входные данные
8 2
kadracyn
2 5
3 4
0 0
0 0
6 8
0 7
0 0
0 0
Выходные данные
daarkkcyan
Входные данные
8 3
kdaracyn
2 5
0 3
0 4
0 0
6 8
0 7
0 0
0 0
Выходные данные
darkcyan
Примечание

Рисунке ниже иллюстрируют примеры. Число в вершине обозначает номер вершины, а строка в нижнем индексе — строку, написанную в вершине. Справа находится строковое представление дерева, где каждая буква имеет цвет соответствующей вершине дерева.

Ниже находится дерево для первого примера. Мы продублировали строки в вершинах $$$1$$$ и $$$3$$$. Строку в вершине $$$2$$$ не нужно дублировать, так как в таком случае представление будет «bbaaab», что лексикографически больше, чем «baaaab».

Во втором примере можно продублировать строки в вершинах $$$1$$$ и $$$2$$$. Обратите внимание, что если продублировать только строку в корне, то представление будет хуже, чем у изначального дерева.

В третьем примере не нужно ничего дублировать. Даже если мы продублируем строку в вершине $$$3$$$, мы будем обязаны также продублировать строку в вершине $$$2$$$, что сделает результат хуже.

Нет способа получить строку «darkkcyan» из дерева с начальным представлением «darkcyan» :(.