# Centroid Decomposition

Authors: Siyong Huang, Benjamin Qi

Decomposing a tree to facilitate path computations.

## Introduction

### Centroids

A **centroid** of a tree is defined as a node such that when the tree is rooted
at it, no other nodes have a subtree of size greater than $\frac{N}{2}$.

Focus Problem – try your best to solve this problem before continuing!

View Internal SolutionWe can find a centroid in a tree by starting at the root. Each step, loop through all of its children. If all of its children have subtree size less than or equal to $\frac{N}{2}$, then it is a centroid. Otherwise, move to the child with a subtree size that is more than $\frac{N}{2}$ and repeat until you find a centroid.

### Implementation

C++

#include <iostream>#include <vector>using namespace std;const int maxn = 200010;int n;vector<int> adj[maxn];int subtree_size[maxn];

Java

import java.io.*;import java.util.*;public class FindCentroid {public static int[] subSize;public static List<Integer>[] adj;public static int N;public static void main(String[] args) {Kattio io = new Kattio();

### Centroid decomposition

Focus Problem – try your best to solve this problem before continuing!

**Centroid Decomposition** is a divide and conquer technique for trees.
**Centroid Decomposition** works by repeated splitting the tree and each of the
resulting subgraphs at the centroid, producing $\mathcal{O}(\log N)$ layers of
subgraphs.

Resources | ||||
---|---|---|---|---|

Carpanese | how to solve above problem | |||

Tanuj Khattar | Illustrated Guide + Problem Walkthrough | |||

robert1003 | Illustrated Guide + Example problems | |||

CF | blog + video for above problem. LCA isn't necessary though. | |||

GFG |

### Warning!

The implementation by
Carpanese
(ll. 20-21) leads to a segmentation fault due to an invalidated iterator in the range-based for loop after erasing the element.
Instead, you can store an `is_removed`

array and check it before visiting children (this approach is presented below).
Alternatively, the following code in the Carpanese article (line 3 is the problematic one):

for (auto v : tree[centroid])tree[centroid].erase(v), // remove the edge to disconnecttree[v].erase(centroid), // the component from the treebuild(v, centroid);

Can be rewritten like so:

for (auto v : tree[centroid]) {tree[v].erase(centroid);build(v, centroid);}tree[centroid].clear();

The article also mentions an update complexity of $\mathcal{O}(\log^2n)$ because it assumes an additional factor of $\mathcal{O}(\log n)$ to calculate the distance between a node and a given centroid ancestor. However, we can precompute these (as demonstrated in the code below) to reduce update complexity to $\mathcal{O}(\log n)$ and overall complexity to $\mathcal{O}((N + Q)\log n)$.

## Implementation

General centroid code is shown below.

C++

vector<vector<int>> adj;vector<bool> is_removed;vector<int> subtree_size;/** DFS to calculate the size of the subtree rooted at `node` */int get_subtree_size(int node, int parent = -1) {subtree_size[node] = 1;for (int child : adj[node]) {if (child == parent || is_removed[child]) { continue; }subtree_size[node] += get_subtree_size(child, node);

Java

private static class Centroid {int n;int[][] g;int[] size;int[] parent;boolean[] seen;Centroid(int n, int[][] g) {this.n = n;this.g = g;

## Solution - Xenia & Tree

For every node, there are at most $\log N$ centroid components that include this node, where $N$ denotes the number of nodes. Let's call the centroid whose component contains one node the centroid ancestor of this node. Also note that the path between every two nodes in the tree must include one of their common centroid ancestors, since the tree is being split into subtrees with the centroids as their respective roots. If we store the distance to the nearest red node for every centroid, we can query the minimal distance between any node and the nearest red node by calculating the minimum distance between the node and one of its centroid ancestors with the minimal distance from that centroid to a red node. To paint a node red, we just update all centroid ancestors of this node. Both operations can be done in $\mathcal{O} (\log N)$ time, as there are at most that many centroid ancestors for one node.

C++

#include <bits/stdc++.h>using namespace std;// a number that is large enough while not causing overflowconst int INF = 1e9;vector<vector<int>> adj;vector<int> subtree_size;// min_dist[v] := the minimal distance between v and a red nodevector<int> min_dist;

## Problems

Status | Source | Problem Name | Difficulty | Tags | |
---|---|---|---|---|---|

CF | Easy | ## Show TagsCentroid | |||

Baltic OI | Easy | ## Show TagsCentroid, Small to Large | |||

CSES | Easy | ## Show TagsCentroid, Small to Large | |||

CSES | Easy | ## Show TagsBIT, Centroid | |||

Old Gold | Easy | ## Show TagsCentroid | |||

IOI | Normal | ## Show TagsCentroid, Merging | |||

Platinum | Normal | ## Show TagsCentroid | |||

CF | Normal | ## Show TagsCentroid | |||

CF | Normal | ## Show TagsCentroid, NT | |||

CF | Normal | ## Show TagsCentroid, DP | |||

JOI | Normal | ## Show TagsCentroid | |||

COCI | Normal | ## Show TagsCentroid, Hashing | |||

DMOPC | Hard | ## Show TagsCentroid | |||

Triway Cup | Hard | ## Show TagsCentroid | |||

JOI | Hard | ## Show TagsCentroid, Small to Large | |||

Platinum | Very Hard | ## Show TagsCentroid |

### Module Progress:

### Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!