Centroid Decomposition
O(n log n) buildRecursively remove the centroid (the vertex whose largest remaining component is smallest), producing a centroid tree of depth O(log n). Any path in the original tree passes through the centroid ancestor of its endpoints, so path-counting problems decompose into per-centroid work.
// use it on
CSES: Fixed-Length Paths I ↗
Count paths of exactly length k: at each centroid, combine depth counts across child branches, then recurse into the pieces.
// the code
// par[u] = parent of u in the centroid tree (-1 for the root).
// Do your per-centroid counting inside build(), before the recursion.
struct CentroidDecomp {
vector<vector<int>> adj;
vector<int> par, sz;
vector<bool> removed;
CentroidDecomp(vector<vector<int>>& g)
: adj(g), par(g.size(), -1), sz(g.size()), removed(g.size(), false) {
build(0, -1);
}
int calc_size(int u, int p) {
sz[u] = 1;
for (int v : adj[u])
if (v != p && !removed[v]) sz[u] += calc_size(v, u);
return sz[u];
}
int find_centroid(int u, int p, int treeSize) {
for (int v : adj[u])
if (v != p && !removed[v] && sz[v] * 2 > treeSize)
return find_centroid(v, u, treeSize);
return u;
}
void build(int u, int p) {
int c = find_centroid(u, -1, calc_size(u, -1));
removed[c] = true;
par[c] = p;
// per-centroid work goes here (BFS/DFS the remaining component)
for (int v : adj[c])
if (!removed[v]) build(v, c);
}
};