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.

#include <iostream>
#include <vector>

using namespace std;

const int maxn = 200010;

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

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.

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];
}

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