# 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 | |||

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

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

#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 | |||

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

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

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

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!