tree/centroid_tree.cpp

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

Verified with

• test/frequency_table_of_tree_distance.test.cpp
• test/vertex_add_range_contour_sum_on_tree.test.cpp
• test/vertex_get_range_contour_add_on_tree.test.cpp

Code

auto centroid_tree(vvi &g) {
  int n = ssize(g);
  vvi tr(n);
  vi sz(n);
  vc<bool> block(n, false);

  auto calc = [&](int v, int p, auto &self) -> void {
    sz[v] = 1;
    for(int x : g[v]) {
      if (x == p or block[x]) continue;
      self(x, v, self);
      sz[v] += sz[x];
    }
  };

  auto dfs = [&](int v, auto &self) -> int {
    calc(v, -1, calc);

    int c = v, p = -1;
    bool move;
    do {
      move = false;
      for(int x : g[c]) {
        if (x == p or block[x] or 2 * sz[x] <= sz[v]) continue;
        move = true, p = c, c = x;
        break;
      }
    } while(move);

    block[c] = true;
    for(int x : g[c]) {
      if (block[x]) continue;
      x = self(x, self);
      tr[c].emplace_back(x);
      tr[x].emplace_back(c);
    }

    return c;
  };

  int root = dfs(0, dfs);

  return pair(tr, root);
}

#line 1 "tree/centroid_tree.cpp"
auto centroid_tree(vvi &g) {
  int n = ssize(g);
  vvi tr(n);
  vi sz(n);
  vc<bool> block(n, false);

  auto calc = [&](int v, int p, auto &self) -> void {
    sz[v] = 1;
    for(int x : g[v]) {
      if (x == p or block[x]) continue;
      self(x, v, self);
      sz[v] += sz[x];
    }
  };

  auto dfs = [&](int v, auto &self) -> int {
    calc(v, -1, calc);

    int c = v, p = -1;
    bool move;
    do {
      move = false;
      for(int x : g[c]) {
        if (x == p or block[x] or 2 * sz[x] <= sz[v]) continue;
        move = true, p = c, c = x;
        break;
      }
    } while(move);

    block[c] = true;
    for(int x : g[c]) {
      if (block[x]) continue;
      x = self(x, self);
      tr[c].emplace_back(x);
      tr[x].emplace_back(c);
    }

    return c;
  };

  int root = dfs(0, dfs);

  return pair(tr, root);
}

Back to top page