Centroid Decomposition
Authors: Siyong Huang, Benjamin Qi
Prerequisites
Decomposing a tree to faciliate 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 .
Focus Problem – read through this problem before continuing!
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 , then it is a centroid. Otherwise, move to the child with a subtree size that is more than and repeat until you find a centroid.
C++
Implementation
#include <iostream>#include <vector>using namespace std;const int maxn = 200010;int n;vector <int> adj[maxn];int subtree_size[maxn];
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 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.
Ben - this is not easy to understand :/
C++
bool r[MN];//removedint s[MN];//subtree sizeint 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
boolean[] r = new boolean[MN];//removedint[] s = new int[MN];//subtree sizepublic 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
Status | Source | Problem Name | Difficulty | Tags | |||||
---|---|---|---|---|---|---|---|---|---|
CF | Easy | Show TagsCentroid | |||||||
Baltic OI | Easy | Show TagsCentroid | |||||||
CSES | Easy | Show TagsCentroid | |||||||
CSES | Easy | Show TagsBIT, Centroid | |||||||
IOI | Normal | Show TagsCentroid, Merging | |||||||
Plat | Normal | Show TagsCentroid | |||||||
CF | Normal | Show TagsCentroid | |||||||
CF | Normal | Show TagsCentroid, NT | |||||||
CF | Normal | Show TagsCentroid, DP | |||||||
JOI | Normal | Show TagsCentroid | |||||||
DMOJ | Hard | Show TagsCentroid | |||||||
DMOJ | Hard | Show TagsCentroid | |||||||
JOI | Hard | Show TagsCentroid, Small to Large | |||||||
Plat | Very 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!