PrevNext
Rare
 0/18

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 N2\frac{N}{2}.

Focus Problem – read through this problem before continuing!

View Internal Solution

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 N2\frac{N}{2}, then it is a centroid. Otherwise, move to the child with a subtree size that is more than N2\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 – 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 O(logN)\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.

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

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

StatusSourceProblem NameDifficultyTags
CFEasy
Show TagsCentroid
Baltic OIEasy
Show TagsCentroid
CSESEasy
Show TagsCentroid
CSESEasy
Show TagsBIT, Centroid
Old GoldEasy
Show TagsCentroid
IOINormal
Show TagsCentroid, Merging
PlatNormal
Show TagsCentroid
CFNormal
Show TagsCentroid
CFNormal
Show TagsCentroid, NT
CFNormal
Show TagsCentroid, DP
JOINormal
Show TagsCentroid
COCINormal
Show TagsCentroid, Hashing
DMOJHard
Show TagsCentroid
DMOJHard
Show TagsCentroid
JOIHard
Show TagsCentroid, Small to Large
PlatVery 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!

PrevNext