Centroid Decomposition

Centroid Decomposition - Course 5

int subtree_size[maxn];

int get_subtree_size(int node, int parent = -1) {
    int &res = subtree_size[node];
    res = 1;
    for (int x : adj[node]) {
        if (x == parent) continue;
        res += get_subtree_size(x, node);
    }
    return res;
}

int get_centroid(int node, int tree_size, int parent = -1) {
    for (int x : adj[node]) {
        if (x == parent) continue;

        if (subtree_size[x] * 2 > tree_size) {
            return get_centroid(x, tree_size, node);
        }
    }
    return node;
}

int get_centroid(int node, int tree_size, int parent = -1) {
    for (int child : adj[node]) {
        if (child == parent || is_removed[child]) continue;
        if (subtree_size[child] * 2 > tree_size) {
            return get_centroid(child, tree_size, node);
        }
    }
    return node;
}

void build_centroid_decomp(int node = 0) {
    int centroid = get_centroid(node, get_subtree_size(node));

    // use centroid to do some magic!

    is_removed[centroid] = true;

    for (int child : adj[centroid]) {
        if (is_removed[child]) continue;
        build_centroid_decomp(child);
    }
}

Centroid Decomposition

Introduction to Centroid Decomposition

Definition of a Centroid

Decomposition Process

Finding the Centroid

Implementation

Decomposition Algorithm

Algorithm Steps

Visualization

Implementation