Rare
0/12

# Centroid Decomposition

Authors: Siyong Huang, Benjamin Qi

### Prerequisites

Decomposing a tree to faciliate path computations.

## Introduction

Focus Problem – read through this problem before continuing!

Centroid Decomposition is a divide and conquer technique for trees. The centroid of a tree is a node which, if rooted, results in no other nodes having a subtree of size greater than $\frac{N}{2}$. Centroid Decomposition works by repeated splitting the tree and each of the resulting subgraphs at the centroid, producing $O(\log N)$ layers of subgraphs.

Resources
Carpanesehow to solve above problem
GFG

## Implementation

General centroid code is shown below.

C++

1bool r[MN];//removed2int s[MN];//subtree size3int dfs(int n, int p = 0)4{5    s[n] = 1;6    for(int x : a[n])7        if(x != p && !r[x])8            s[n] += dfs(x, n);9    return s[n];10}

Java

1boolean[] r = new boolean[MN];//removed2int[] s = new int[MN];//subtree size3public int dfs(int n, int p)4{5    s[n] = 1;6    for(int x : a[n])7        if(x != p && !r[x])8            s[n] += dfs(x, n);9    return s[n];10}

## Solution - Xenia & Tree

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

## Problems

StatusSourceProblem NameDifficultyTagsSolution
CFEasy
Show Tags

Centroid

Check CF
CFEasy
Show Tags

Centroid

Check CF
PlatNormal
Show Tags

Centroid

External Sol
CFNormal
Show Tags

Centroid

Check CF
CFNormal
Show Tags

Centroid, NT

Check CF
CFNormal
Show Tags

Centroid, DP

Check CF
JOINormal
Show Tags

Centroid

External Sol
DMOJHard
Show Tags

Centroid

DMOJHard
Show Tags

Centroid

JOIHard
Show Tags

Centroid, Small to Large

PlatVery Hard
Show Tags

Centroid

External Sol