Centroid Decomposition

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}$.

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

Copy
#include <iostream>
#include <vector>

using namespace std;

const int maxn = 200010;

int n;
vector<int> adj[maxn];
int subtree_size[maxn];

Copy
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

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.

Implementation

General centroid code is shown below.

Copy
vector<int> adj[maxn];  // adjacency list
bool is_removed[MN];
int subtree_size[MN];

int dfs(int u, int parent = 0) {
	subtree_size[u] = 1;
	for (int v : adj[u]) {
		if (v != parent && !is_removed[v]) { subtree_size[u] += dfs(v, u); }
	}

Copy
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

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

Problems