# Centroid Decomposition

Authors: Siyong Huang, Benjamin Qi

### Prerequisites

Decomposing a tree to faciliate 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 – read through this problem before continuing!

We 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.

C++

### Implementation

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

### Centroid decomposition

Focus Problem – read through 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 | ||

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

GFG |

## Implementation

General centroid code is shown below.

### This section is not complete.

Ben - this is not easy to understand :/

C++

bool r[MN];//removedint s[MN];//subtree sizeint dfs(int n, int p = 0){s[n] = 1;for(int x : a[n])if(x != p && !r[x])s[n] += dfs(x, n);return s[n];}

Java

boolean[] r = new boolean[MN];//removedint[] s = new int[MN];//subtree sizepublic int dfs(int n, int p){s[n] = 1;for(int x : a[n])if(x != p && !r[x])s[n] += dfs(x, n);return s[n];}

## Solution - Xenia & Tree

#include <cstdio>#include <cstring>#include <vector>template<typename T> bool ckmin(T& a, const T& b){return b<a?a=b,1:0;}const int MN = 1e5+10, INF = 0x3f3f3f3f;int N, M, s[MN], m[MN][2], t, b, d;bool r[MN], red[MN];

## Problems

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

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

Baltic OI | Easy | ## Show TagsCentroid | |||||||

CSES | Easy | ## Show TagsCentroid | |||||||

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

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

Plat | Normal | ## Show TagsCentroid | |||||||

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

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

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

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

DMOJ | Hard | ## Show TagsCentroid | |||||||

DMOJ | Hard | ## Show TagsCentroid | |||||||

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

Plat | 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!