treeBinaryTransform

template <typename T>
std::vector<std::vector<std::pair<T, int>>> treeBinaryTransform(std::vector<std::vector<std::pair<T, int>>> g, int root = 0, bool bidirectional = true) {
  int n = int(g.size());
  assert(0 <= root && root < n);
  int new_node = n;
  std::vector<std::vector<std::pair<T, int>>> res_g(2 * n);

  auto dfs = [&](auto&& dfs, int from, int to, int idx) -> void {
    for (int i = idx; i < int(g[from].size()); ++i) {
      if (res_g[to].empty() || i == int(g[from].size()) - 1) {
        res_g[to].push_back(g[from][i]);
        if (bidirectional) {
          g[g[from][i].second].erase(std::find(g[g[from][i].second].begin(), g[g[from][i].second].end(), std::pair {g[from][i].first, from}));
        }
        dfs(dfs, g[from][i].second, g[from][i].second, 0);
      } else {
        res_g[to].emplace_back(0, new_node);
        dfs(dfs, from, new_node++, i);
        break;
      }
    }
  };

  dfs(dfs, 0, 0, 0);
  return res_g;
}