Centroid, CentroidTree

struct Centroid {
  int n;
  std::vector<std::vector<int>> g;
  std::vector<bool> done;
  std::vector<int> siz;

  Centroid(int n) : n(n), g(n), done(n), siz(n) {
    void(0);
  }

  const std::vector<int>& operator[](int idx) const {
    assert(0 <= idx && idx < n);
    return g[idx];
  }

  void addEdge(int u, int v) {
    assert(0 <= u && u < n);
    assert(0 <= v && v < n);
    assert(u != v);
    g[u].push_back(v);
    g[v].push_back(u);
  }

  void getSizeImpl(int u, int p) {
    siz[u] = 1;
    for (int v : g[u]) {
      if (v == p || done[v]) {
        continue;
      }
      getSizeImpl(v, u);
      siz[u] += siz[v];
    }
  }

  int getCentImpl(int u, int p, int tot) {
    for (int v : g[u]) {
      if (v != p && !done[v] && siz[v] + siz[v] > tot) {
        return getCentImpl(v, u, tot);
      }
    }
    return u;
  }

  int getCent(int u) {
    assert(0 <= u && u < n);
    assert(!done[u]);
    getSizeImpl(u, -1);
    u = getCentImpl(u, -1, siz[u]);
    done[u] = true;
    return u;
  }
};

struct CentroidTree : Centroid {
  std::vector<int> par;

  CentroidTree(int n) : Centroid(n), par(n, -1) {
    void(0);
  }

  int work(int u = 0) {
    u = getCent(u);
    for (int v : g[u]) {
      if (!done[v]) {
        par[work(v)] = u;
      }
    }
    return u;
  }
};