PrevNext
Rare
 0/12

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 N2\frac{N}{2}. Centroid Decomposition works by repeated splitting the tree and each of the resulting subgraphs at the centroid, producing O(logN)O(\log N) layers of subgraphs.

Implementation

General centroid code is shown below.

C++

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

Module Progress:

Give Us Feedback on Centroid Decomposition!

PrevNext