vi. Centroid Decomposition

Remove a centroid, recurse on the remaining components. The recursion (the centroid tree) has depth $\le {\log }_{2}n$, each vertex lies in $O(\log n)$ components, and every path of the tree passes through exactly one “highest” centroid. So “count / optimise over all paths” problems are solved by handling the paths through each centroid, and the centroid tree doubles as an index for distance queries with updates.

Problem	Per centroid
paths of length exactly $K$ / at most $K$	depth counts, branch by branch (or sort + two pointers)
paths of every length	square the depth histogram (FFT) minus each branch’s square, $O(n{\log }^{2}n)$
paths with xor / sum / colour condition	hash map of branch values, query before insert
nearest marked vertex, marks added online	centroid tree index: $O(\log n)$ per operation
sum of distances to a dynamic set	per centroid: count and distance sums (with the parent correction)
shortest path with $\le k$ edges and weight $W$	best edges per weight in a map / array, cleared per centroid
add $x$ to every vertex within distance $d$ of a query point	update along the centroid ancestors, same shape as the centroid-tree index below
paths with at most $k$ “bad” edges (CF 161D, Codechef PRIMEDST style)	2D counting (depth, bad-edge count) with a BIT per centroid

Driver: solve the paths through each centroid

template <class F> void centroidDC(const vector<vector<pair<int, ll>>>& adj, F solve) {
    // solve(c, branches): branches[i] = list of (vertex, dist to c) for the i-th component hanging off c
    int n = sz(adj); vector<char> removed(n); vector<int> sub(n), from(n); vector<int> todo{0};
    while (sz(todo)) {
        int s = todo.back(); todo.pop_back();
        vector<int> order{s}; from[s] = -1;
        for (int i = 0; i < sz(order); i++) for (auto [v, w] : adj[order[i]]) if (v != from[order[i]] && !removed[v]) from[v] = order[i], order.push_back(v);
        for (int i = sz(order) - 1; i >= 0; i--) { int u = order[i]; sub[u] = 1; for (auto [v, w] : adj[u]) if (v != from[u] && !removed[v]) sub[u] += sub[v]; }
        int tot = sz(order), c = s;
        for (bool mv = true; mv;) { mv = false; for (auto [v, w] : adj[c]) if (v != from[c] && !removed[v] && 2 * sub[v] > tot) { c = v, mv = true; break; } }
        removed[c] = 1; vector<vector<pair<int, ll>>> branches;
        for (auto [v, w] : adj[c]) if (!removed[v]) {
            vector<pair<int, ll>> b{{v, w}}; vector<int> par{c};
            for (int i = 0; i < sz(b); i++) for (auto [x, wx] : adj[b[i].first]) if (x != par[i] && !removed[x]) b.push_back({x, b[i].second + wx}), par.push_back(b[i].first);
            branches.push_back(move(b)); todo.push_back(v);
        }
        solve(c, branches);
    }
}
ll countPathsOfLength(const vector<vector<pair<int, ll>>>& adj, ll K) {   // unordered pairs at distance exactly K (K >= 1)
    ll ans = 0;
    centroidDC(adj, [&](int c, auto& branches) {
        map<ll, ll> seen{{0, 1}};                          // the centroid itself
        for (auto& b : branches) {
            for (auto [v, d] : b) if (auto it = seen.find(K - d); it != seen.end()) ans += it->second;   // query first
            for (auto [v, d] : b) seen[d]++;                                                            // then insert
        }
    });
    return ans;
}
template <class Conv> vector<ll> pathsOfEachLength(const vector<vector<int>>& g, Conv conv) {   // cnt[d], d >= 1; cnt[0] = n
    int n = sz(g); vector<vector<pair<int, ll>>> adj(n); for (int u = 0; u < n; u++) for (int v : g[u]) adj[u].push_back({v, 1});
    vector<ll> cnt(n); if (n) cnt[0] = n;
    auto addSq = [&](const vector<ll>& h, ll sign) { auto sq = conv(h, h); for (int d = 1; d < sz(sq) && d < n; d++) cnt[d] += sign * sq[d]; };
    centroidDC(adj, [&](int c, auto& branches) {
        vector<ll> all{1};
        for (auto& b : branches) {
            vector<ll> h; for (auto [v, d] : b) { if (sz(h) <= d) h.resize(d + 1); h[d]++; if (sz(all) <= d) all.resize(d + 1); all[d]++; }
            addSq(h, -1);
        }
        addSq(all, 1);
    });
    for (int d = 1; d < n; d++) cnt[d] /= 2;                // ordered -> unordered
    return cnt;
}

conv is any exact integer convolution: FFT with rounding (FFT) is exact while counts stay below about $10^{15}$. Variants worth recognising: restricting to distances in $[L,R]$ (two-pointer or binary-search on the same histograms instead of full convolution), and “count unordered pairs at distance exactly $K$” without the full per-length table (CF 161D, Codechef PRIMEDST).

Proof: depth, total work, and why every path is counted once

Depth: every component of $T-c$ has at most half the vertices of $T$, so the component sizes halve level by level and the recursion depth is $\le {\log }_{2}n+1$. Each level partitions a subset of the vertices, so the work per level is $O(n)$ (plus the per-centroid solver) and the total is $O(n\log n)$. The walk to the centroid stops at a vertex whose child components (in the rooting at $s$) have $\le$ half, and the part above has $<$ half because the walk only descends into a child of size $>\text{tot}/2$.

Paths: for a path $P$ (with at least two vertices), consider the first centroid chosen that lies on $P$. Before it, $P$ was never cut, so $P$ lies in that centroid’s component and passes through it; afterwards $P$ is split. So each path is handled at exactly one centroid, where it consists of two parts in different branches, or one part plus the centroid itself. Query-before-insert pairs each vertex only with vertices of earlier branches and with the centroid, counting every such pair once. All lengths: $(\text{all}{)}^2[d]$ counts ordered pairs $(x,y)$ of the component’s vertices (including $c$) with $d_x+d_y=d$; subtracting each branch’s square removes the pairs inside one branch, which do not pass through $c$; for $d\ge 1$ the remaining pairs are exactly the ordered pairs at distance $d$ whose path’s highest centroid is $c$. The convolution sizes are bounded by the component’s size, $O(m\log m)$ per component, $O(n{\log }^{2}n)$ in total.

Centroid tree as an index

Store, for every vertex, its distance to each of its $O(\log n)$ centroid ancestors (or skip the precomputation and answer each dist with LCA in $O(\log n)$ instead — simpler, same complexity, slightly slower in practice). For any $x,v$, $\text{dist}(x,v)=\text{dist}(x,c)+\text{dist}(c,v)$ where $c$ is their lowest common ancestor in the centroid tree, and $\le$ for every other common centroid ancestor.

struct CentroidTree {                                     // cpar, lvl, dist[l][v] = dist(v, its level-l centroid ancestor)
    int n, root = -1; vector<int> cpar, lvl; vector<vector<ll>> dist;
    CentroidTree(const vector<vector<pair<int, ll>>>& adj) : n(sz(adj)), cpar(n, -1), lvl(n, -1) {
        vector<int> sub(n), from(n); vector<pair<int, int>> todo{{0, -1}};
        while (sz(todo) && n) {
            auto [s, above] = todo.back(); todo.pop_back();
            vector<int> order{s}; from[s] = -1;
            for (int i = 0; i < sz(order); i++) for (auto [v, w] : adj[order[i]]) if (v != from[order[i]] && lvl[v] < 0) from[v] = order[i], order.push_back(v);
            for (int i = sz(order) - 1; i >= 0; i--) { int u = order[i]; sub[u] = 1; for (auto [v, w] : adj[u]) if (v != from[u] && lvl[v] < 0) sub[u] += sub[v]; }
            int tot = sz(order), c = s;
            for (bool mv = true; mv;) { mv = false; for (auto [v, w] : adj[c]) if (v != from[c] && lvl[v] < 0 && 2 * sub[v] > tot) { c = v, mv = true; break; } }
            cpar[c] = above; lvl[c] = above < 0 ? 0 : lvl[above] + 1; if (above < 0) root = c;
            int L = lvl[c]; if (L == sz(dist)) dist.emplace_back(n, -1);
            dist[L][c] = 0; vector<int> q{c};
            for (int i = 0; i < sz(q); i++) for (auto [v, w] : adj[q[i]]) if (lvl[v] < 0 && dist[L][v] < 0) dist[L][v] = dist[L][q[i]] + w, q.push_back(v);
            for (auto [v, w] : adj[c]) if (lvl[v] < 0) todo.push_back({v, c});
        }
    }
    ll d(int v, int c) const { return dist[lvl[c]][v]; }   // c must be a centroid ancestor of v
};
struct NearestMarked {                                    // mark vertices online; distance to the nearest marked one
    const CentroidTree& ct; vector<ll> best; static constexpr ll INF = LLONG_MAX / 4;
    NearestMarked(const CentroidTree& ct) : ct(ct), best(ct.n, INF) {}
    void mark(int v) { for (int c = v; c >= 0; c = ct.cpar[c]) best[c] = min(best[c], ct.d(v, c)); }
    ll query(int v) const { ll r = INF; for (int c = v; c >= 0; c = ct.cpar[c]) r = min(r, best[c] + ct.d(v, c)); return r; }
};
struct DistanceSum {                                      // multiset S under insert/erase; sum of dist(v, x) over x in S
    const CentroidTree& ct; vector<ll> cnt, sum, sumPar;  // sumPar[c]: distances to cpar[c] from S inside c's component
    DistanceSum(const CentroidTree& ct) : ct(ct), cnt(ct.n), sum(ct.n), sumPar(ct.n) {}
    void add(int x, int s = 1) {
        for (int c = x; c >= 0; c = ct.cpar[c]) { cnt[c] += s; sum[c] += s * ct.d(x, c); if (ct.cpar[c] >= 0) sumPar[c] += s * ct.d(x, ct.cpar[c]); }
    }
    ll query(int v) const {
        ll r = 0;
        for (int c = v, prev = -1; c >= 0; prev = c, c = ct.cpar[c]) {
            r += sum[c] + cnt[c] * ct.d(v, c);
            if (prev >= 0) r -= sumPar[prev] + cnt[prev] * ct.d(v, c);   // those were counted through prev already
        }
        return r;
    }
};

Proof: the centroid-LCA distance identity

Let $c$ be the lowest common centroid ancestor of $x$ and $v$. Both lie in $c$‘s component, and in different child components (or one of them is $c$), since otherwise the child centroid would be a deeper common ancestor. The path between them stays inside $c$‘s component (components are connected and the path between two vertices of a subtree stays in it), and since they are separated by removing $c$, it passes through $c$: $\text{dist}(x,v)=\text{dist}(x,c)+\text{dist}(c,v)$, with both distances measured inside the component, which equal the tree distances. For any other common ancestor the triangle inequality gives $\ge$. NearestMarked takes the minimum over all common ancestors, which includes the exact one. DistanceSum: walking up from $v$, the term at $c$ adds $\text{dist}(x,c)+\text{dist}(c,v)$ for every $x$ in $c$‘s component, then subtracts those $x$ in the previous (child) component, whose deepest common ancestor with $v$ is lower and was already counted there; each $x$ is counted exactly once, at the centroid-LCA.

Edge-centroid decomposition

Binarise (degree $\le 3$, Tree Basics) and cut the edge splitting the component most evenly: both sides have at least about a third. Every path is handled at exactly one cut edge, as a pair (one vertex on each side) with length $d_a+w+d_b$. Only two parts per step, which makes merging two sides simple: two sorted lists (e.g. counting pairs by distance: sort one side, two pointers on the other) or two convex hulls (e.g. “max over pairs of $a_x+a_y+\text{dist}(x,y)$ with linear functions”).

template <class F> void edgeCentroidDC(const vector<vector<pair<int, ll>>>& tree, F callback) {
    // callback(A, B, w): A, B = (vertex, distance to the cut edge's endpoint on its side); vertices >= n are dummies
    int n = sz(tree); if (n <= 1) return;
    auto g = binarizeTree(tree, 0); int N = sz(g);
    vector<vector<array<ll, 3>>> adj(N); int ids = 0;               // (to, weight, edge id)
    for (int u = 0; u < N; u++) for (auto [v, w] : g[u]) if (u < v) adj[u].push_back({v, w, ids}), adj[v].push_back({u, w, ids}), ids++;
    vector<char> removed(ids); vector<int> sub(N); vector<int> todo{0};
    auto collect = [&](int s, vector<pair<int, ll>>& out) {
        vector<tuple<int, int, ll>> st{{s, -1, 0}};
        while (sz(st)) { auto [v, p, d] = st.back(); st.pop_back(); out.push_back({v, d});
            for (auto [to, w, id] : adj[v]) if (to != p && !removed[id]) st.push_back({(int)to, v, d + w}); }
    };
    while (sz(todo)) {
        int root = todo.back(); todo.pop_back();
        vector<int> order, par; vector<pair<int, int>> st{{root, -1}};
        while (sz(st)) { auto [v, p] = st.back(); st.pop_back(); order.push_back(v), par.push_back(p);
            for (auto [to, w, id] : adj[v]) if (to != p && !removed[id]) st.push_back({(int)to, v}); }
        int cnt = sz(order); if (cnt <= 1) continue;
        for (int v : order) sub[v] = 1;
        for (int i = cnt - 1; i > 0; i--) sub[par[i]] += sub[order[i]];
        int best = -1, val = INT_MAX;
        for (int i = 1; i < cnt; i++) if (int v = max(sub[order[i]], cnt - sub[order[i]]); v < val) val = v, best = i;
        int c = order[best], p = par[best]; ll w = 0;
        for (auto [to, ww, id] : adj[c]) if (to == p && !removed[id]) { w = ww, removed[id] = 1; break; }
        vector<pair<int, ll>> A, B; collect(p, A), collect(c, B);
        callback(A, B, w);
        todo.push_back(p), todo.push_back(c);
    }
}

Proof: balanced edge cuts with degree $\le 3$

Let $c$ be a vertex centroid of the current component of size $m$: every component of the component minus $c$ has $\le m/2$ vertices, there are at most 3 of them, and they hold $m-1$ vertices, so the largest has size $s\ge (m-1)/3$. Cutting the edge from $c$ to it leaves sides of sizes $s\le m/2$ and $m-s\ge m/2$, so the larger side has $\le m-(m-1)/3=(2m+1)/3$ vertices; the chosen edge is at least as balanced. Sizes shrink geometrically (factor $\approx 2/3$), so the depth is $O(\log n)$ and the total size of all callback lists is $O(n\log n)$. A path between two vertices is handled at the first cut edge lying on it, where its endpoints are on opposite sides, and its length is $d_a+w+d_b$ (binarisation preserves distances between original vertices).

Persistent centroid tree

Versions of a multiset (each version = an older one plus a vertex) with online “sum of distances from $v$ to version $k$”: binarise so each centroid has $\le 3$ children and path-copy the $O(\log n)$ nodes on the inserted vertex’s centroid-ancestor chain. Classic use: a permutation $p$ of vertices, version $i=\{p_0,\dots ,p_{i-1}\}$, and ${\sum }_{l\le i<r}\text{dist}(v,p_i)=\text{query}(r,v)-\text{query}(l,v)$.

struct PersistentCentroid {
    struct Node { array<int, 3> ch{0, 0, 0}; ll cnt = 0, sum = 0, sumPar = 0; };
    int N; vector<vector<pair<int, ll>>> g; vector<int> cpar, clevel; vector<vector<ll>> dist; vector<vector<int>> childIdx;
    vector<Node> t{Node()}; vector<int> versions{0};
    PersistentCentroid(const vector<vector<pair<int, ll>>>& adj) {
        g = adj.empty() ? adj : binarizeTree(adj, 0); N = sz(g); cpar.assign(N, -1), clevel.assign(N, -1);
        vector<int> siz(N), from(N); vector<pair<int, int>> todo{{0, -1}};
        while (sz(todo) && N) {
            auto [s, above] = todo.back(); todo.pop_back();
            vector<int> order{s}; from[s] = -1;
            for (int i = 0; i < sz(order); i++) for (auto [v, w] : g[order[i]]) if (v != from[order[i]] && clevel[v] < 0) from[v] = order[i], order.push_back(v);
            for (int i = sz(order) - 1; i >= 0; i--) { int u = order[i]; siz[u] = 1; for (auto [v, w] : g[u]) if (v != from[u] && clevel[v] < 0) siz[u] += siz[v]; }
            int total = sz(order), c = s;
            for (bool mv = true; mv;) { mv = false; for (auto [v, w] : g[c]) if (v != from[c] && clevel[v] < 0 && 2 * siz[v] > total) { c = v, mv = true; break; } }
            cpar[c] = above; clevel[c] = above < 0 ? 0 : clevel[above] + 1;
            int L = clevel[c]; if (L == sz(dist)) dist.emplace_back(N, -1), childIdx.emplace_back(N, -1);
            dist[L][c] = 0; vector<int> q{c}; int k = 0;
            for (auto [v, w] : g[c]) if (clevel[v] < 0) dist[L][v] = w, childIdx[L][v] = k++, q.push_back(v);
            for (int i = 1; i < sz(q); i++) for (auto [v, w] : g[q[i]]) if (clevel[v] < 0 && dist[L][v] < 0) dist[L][v] = dist[L][q[i]] + w, childIdx[L][v] = childIdx[L][q[i]], q.push_back(v);
            for (auto [v, w] : g[c]) if (clevel[v] < 0) todo.push_back({v, c});
        }
    }
    vector<int> chainOf(int v) const { vector<int> ch; for (int c = v; c >= 0; c = cpar[c]) ch.push_back(c); reverse(all(ch)); return ch; }
    int insert(int version, int x) {                       // returns the new version id
        auto chain = chainOf(x); int old = versions[version], root = sz(t); t.push_back(t[old]);
        for (int i = 0, cur = root, po = old; i < sz(chain); i++) {
            int c = chain[i], L = clevel[c];
            t[cur].cnt++, t[cur].sum += dist[L][x]; if (L > 0) t[cur].sumPar += dist[L - 1][x];
            if (i + 1 == sz(chain)) break;
            int k = childIdx[L][x], oc = t[po].ch[k], nc = sz(t); t.push_back(t[oc]); t[cur].ch[k] = nc; cur = nc, po = oc;
        }
        versions.push_back(root); return sz(versions) - 1;
    }
    ll query(int version, int v) const {                   // sum of dist(v, x) over x in the version
        auto chain = chainOf(v); int node = versions[version]; ll res = 0;
        for (int i = 0; i < sz(chain); i++) {
            int L = clevel[chain[i]]; const Node& nd = t[node];
            res += nd.sum + nd.cnt * dist[L][v];
            if (i + 1 == sz(chain)) break;
            const Node& ch = t[nd.ch[childIdx[L][v]]];
            res -= ch.sumPar + ch.cnt * dist[L][v]; node = nd.ch[childIdx[L][v]];
        }
        return res;
    }
};

The query is the DistanceSum formula read from a persistent copy: node $0$ is an all-zero sentinel, and each insert copies only the nodes on one root-to-node chain of the centroid tree ($O(\log n)$ time and memory).