Centroid Decomposition

Introduction

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

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}

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