Centroid Decomposition
Authors: Siyong Huang, Benjamin Qi
Decomposing a tree to facilitate 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!
View Internal SolutionWe 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.
Implementation
C++
#include <iostream>#include <vector>using namespace std;const int maxn = 200010;int n;vector <int> adj[maxn];int subtree_size[maxn];
Java
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
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
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
#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 | |||
Old Gold | Easy | Show TagsCentroid | |||
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 | |||
COCI | Normal | Show TagsCentroid, Hashing | |||
DMOJ | Hard | Show TagsCentroid | |||
DMOJ | Hard | Show TagsCentroid | |||
JOI | Hard | Show TagsCentroid, Small to Large | |||
Plat | Very Hard | Show TagsCentroid |