PrevNext
Rare
 0/13

Centroid Decomposition

Authors: Siyong Huang, Benjamin Qi

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 . Centroid Decomposition works by repeated splitting the tree and each of the resulting subgraphs at the centroid, producing layers of subgraphs.

Resources
Carpanesehow to solve above problem
CFblog + video for above problem. LCA isn't necessary though.
GFG

Implementation

General centroid code is shown below.

This section is not complete.

Any help would be appreciated! Just submit a Pull Request on Github.

Ben - this is not easy to understand :/

C++

bool r[MN];//removed
int s[MN];//subtree size
int 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];//removed
int[] s = new int[MN];//subtree size
public 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

StatusSourceProblem NameDifficultyTagsSolutionURL
CFEasy
Show Tags

Centroid

Check CF
Baltic OIEasy
Show Tags

Centroid

Check CF
IOINormal
Show Tags

Centroid, Merging

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

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!

Give Us Feedback on Centroid Decomposition!

Leave suggestions for us by making a post on the USACO Forum! Ex: Unclear sections, mislabeled problems, etc.

PrevNext