description: 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} <empty string>, & if u = 0; \\\ f(l_u) + c_u + f(r_u) & 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 ≠ 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. 
  
  Input
  
  The first line contains two integers n and k (1 ≤ k ≤ n ≤ 2 ⋅ 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 ≤ i ≤ 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 ≤ l_i, r_i ≤ 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.
  
  Output
  
  Print a single line, containing the lexicographically smallest string representation of the tree if at most k nodes have their labels duplicated.
  
  Examples
  
  Input
  
  
  4 3
  abab
  2 3
  0 0
  0 4
  0 0
  
  
  Output
  
  
  baaaab
  
  Input
  
  
  8 2
  kadracyn
  2 5
  3 4
  0 0
  0 0
  6 8
  0 7
  0 0
  0 0
  
  
  Output
  
  
  daarkkcyan
  
  Input
  
  
  8 3
  kdaracyn
  2 5
  0 3
  0 4
  0 0
  6 8
  0 7
  0 0
  0 0
  
  
  Output
  
  
  darkcyan
  
  Note
  
  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".
  
  <image>
  
  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.
  
  <image>
  
  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.
  
  <image>
  
  There is no way to produce string "darkkcyan" from a tree with the initial string representation "darkcyan" :(.
solution: #include <bits/stdc++.h>
  using namespace std;
  const int maxn = 202020;
  int n, k;
  string c;
  int l[maxn], r[maxn];
  vector<int> in_order;
  void build_in_order(int u) {
    if (u == 0) return;
    build_in_order(l[u]);
    in_order.push_back(u);
    build_in_order(r[u]);
  }
  bool good[maxn];
  bool duplicated[maxn];
  void dfs(int u, int cost = 1) {
    if (u == 0) return;
    if (cost > k) return;
    dfs(l[u], cost + 1);
    if (duplicated[l[u]]) {
      duplicated[u] = true;
    } else if (good[u]) {
      duplicated[u] = true;
      k -= cost;
    }
    if (duplicated[u]) dfs(r[u], 1);
  }
  int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> k;
    cin >> c;
    c = ' ' + c;
    for (int i = 1; i <= n; ++i) {
      cin >> l[i] >> r[i];
    }
    build_in_order(1);
    char last_diff = c[in_order.back()];
    for (int i = n - 2; i >= 0; --i) {
      int u = in_order[i];
      int v = in_order[i + 1];
      if (c[u] != c[v]) {
        last_diff = c[v];
      }
      if (c[u] < last_diff) {
        good[u] = true;
      }
    }
    dfs(1);
    for (auto u : in_order) {
      cout << c[u];
      if (duplicated[u]) cout << c[u];
    }
    return 0;
  }
  