tree/prufer_recover.cpp

• View this file on GitHub
• Last update: 2026-02-02 01:08:31+08:00
• Link: View error logs on GitHub Actions

Verified with

• test/mytest_auxiliary_tree.test.cpp
• test/mytest_tree.test.cpp
• test/mytest_tree_diameter.test.cpp

Code

//empty vector would be assumed to be n = 2
vc<pii> prufer_recover(vi prufer_code) {
  const int n = ssize(prufer_code) + 2;
  assert(prufer_code.empty() or (ranges::min(prufer_code) >= 0 and ranges::max(prufer_code) < n));
  vi d(n, 1);
  for(int x : prufer_code) d[x]++;
  min_heap<int> leaf;
  for(int v = 0; v < n; v++)
    if (d[v] == 1)
      leaf.emplace(v);
  vc<pii> edges;
  for(int x : prufer_code) {
    int v = leaf.top(); leaf.pop();
    edges.emplace_back(v, x);
    if (--d[x] == 1)
      leaf.emplace(x);
  }
  int v = leaf.top(); leaf.pop();
  edges.emplace_back(v, leaf.top());
  return edges;
}

#line 1 "tree/prufer_recover.cpp"
//empty vector would be assumed to be n = 2
vc<pii> prufer_recover(vi prufer_code) {
  const int n = ssize(prufer_code) + 2;
  assert(prufer_code.empty() or (ranges::min(prufer_code) >= 0 and ranges::max(prufer_code) < n));
  vi d(n, 1);
  for(int x : prufer_code) d[x]++;
  min_heap<int> leaf;
  for(int v = 0; v < n; v++)
    if (d[v] == 1)
      leaf.emplace(v);
  vc<pii> edges;
  for(int x : prufer_code) {
    int v = leaf.top(); leaf.pop();
    edges.emplace_back(v, x);
    if (--d[x] == 1)
      leaf.emplace(x);
  }
  int v = leaf.top(); leaf.pop();
  edges.emplace_back(v, leaf.top());
  return edges;
}

Back to top page