Descomposición por centroide

Introducción

Centroides

Un centroide de un árbol se define como un nodo tal que, cuando el árbol se enraíza en él, ningún otro nodo tiene un subárbol de tamaño mayor que $\frac{N}{2}$ .

Hecho	Fuente	Nombre	Dificultad	Tags	Solución
	CSES	Finding a Centroid	Muy fácil		Solución

Podemos hallar un centroide en un árbol empezando por la raíz. En cada paso, recorremos todos sus hijos. Si todos los hijos tienen tamaño de subárbol menor o igual que $\frac{N}{2}$ , entonces es un centroide. Si no, nos movemos al hijo con tamaño de subárbol mayor que $\frac{N}{2}$ y repetimos hasta hallar un centroide.

Implementación

C++JavaPython


#include <iostream>
#include <vector>
 
using namespace std;
 
const int maxn = 200010;
 
int n;
vector<int> adj[maxn];
int subtree_size[maxn];
 
int get_subtree_size(int node, int parent = -1) {
	int &res = subtree_size[node];
	res = 1;
	for (int i : adj[node]) {
		if (i == parent) { continue; }
		res += get_subtree_size(i, node);
	}
	return res;
}
 
int get_centroid(int node, int parent = -1) {
	for (int i : adj[node]) {
		if (i == parent) { continue; }
 
		if (subtree_size[i] * 2 > n) { return get_centroid(i, node); }
	}
	return node;
}
 
int main() {
	cin >> n;
	for (int i = 0; i < n - 1; i++) {
		int a, b;
		cin >> a >> b;
		a--;
		b--;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
 
	get_subtree_size(0);
	cout << get_centroid(0) + 1 << endl;
}


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();
		N = io.nextInt();
		adj = new List[N];
		for (int i = 0; i < N; i++) { adj[i] = new ArrayList<>(); }
		subSize = new int[N];
 
		for (int i = 0; i < N - 1; i++) {
			int a = io.nextInt() - 1;
			int b = io.nextInt() - 1;
			adj[a].add(b);
			adj[b].add(a);
		}
 
		subtreeSize(0, -1);
		io.println(getCentroid(0, -1) + 1);
		io.close();
	}
 
	// Hallar el tamaño del subárbol bajo este nodo.
	public static int subtreeSize(int node, int par) {
		int res = 1;
		for (int next : adj[node]) {
			if (next == par) { continue; }
			res += subtreeSize(next, node);
		}
		return (subSize[node] = res);
	}
 
	// Hallar el centroide del árbol (el subárbol con <= N/2 nodos)
	public static int getCentroid(int node, int par) {
		for (int next : adj[node]) {
			if (next == par) { continue; }
			// Seguir buscando el centroide si hay subárboles con más
			// de N/2 nodos.
			if (subSize[next] * 2 > N) { return getCentroid(next, node); }
		}
		return node;
	}
	// CodeSnip{Kattio}
}


import sys
 
# Aumentar la profundidad de recursión para manejar la profundidad máxima del árbol
sys.setrecursionlimit(200050)
 
maxn = 200010
 
n = 0
adj = [[] for _ in range(maxn)]
subtree_size = [0] * maxn
 
 
def get_subtree_size(node, parent=-1):
	res = 1
	for i in adj[node]:
		if i == parent:
			continue
		res += get_subtree_size(i, node)
 
	subtree_size[node] = res
	return res
 
 
def get_centroid(node, parent=-1):
	for i in adj[node]:
		if i == parent:
			continue
 
		if subtree_size[i] * 2 > n:
			return get_centroid(i, node)
 
	return node
 
 
def main():
	global n
 
	# Leer toda la entrada estándar, como el parseo de tokens de cin
	tokens = sys.stdin.read().split()
	if not tokens:
		return
 
	n = int(tokens[0])
 
	ptr = 1
	for i in range(n - 1):
		a = int(tokens[ptr])
		b = int(tokens[ptr + 1])
		ptr += 2
 
		a -= 1
		b -= 1
		adj[a].append(b)
		adj[b].append(a)
 
	get_subtree_size(0)
	print(get_centroid(0) + 1)
 
 
if __name__ == "__main__":
	main()

Descomposición por centroide

Hecho	Fuente	Nombre	Dificultad	Tags	Solución
	CF	Xenia & Tree	Normal	Centroid	en el módulo

La descomposición por centroide (Centroid Decomposition) es una técnica de divide y vencerás para árboles. La descomposición por centroide funciona partiendo el árbol de forma repetida, y cada uno de los subgrafos resultantes, en el centroide, y produce $\mathcal{O}(\log N)$ capas de subgrafos.

Recursos
Fuente	Recurso	Notas
Carpanese	Illustrated Intro to Centroid Decomposition	cómo resolver el problema de arriba
Tanuj Khattar	Centroid Decomposition of a Tree	Guía ilustrada + recorrido del problema
robert1003	A Simple Introduction to Centroid Decomposition	Guía ilustrada + problemas de ejemplo
CF	galen_colin - Centroid Decomposition	blog + video del problema de arriba. El LCA no es necesario, igual.
GFG	Centroid Decomposition of Tree

La implementación de Carpanese (ll. 20-21) provoca un segmentation fault por un iterador invalidado en el bucle for por rango después de borrar el elemento. En su lugar, se puede guardar un arreglo is_removed y chequearlo antes de visitar a los hijos (este enfoque se presenta más abajo). Como alternativa, el siguiente código del artículo de Carpanese (la línea 3 es la problemática):


for (auto v : tree[centroid])
	tree[centroid].erase(v),      // remove the edge to disconnect
	    tree[v].erase(centroid),  // the component from the tree
	    build(v, centroid);

Se puede reescribir así:


for (auto v : tree[centroid]) {
	tree[v].erase(centroid);
	build(v, centroid);
}
tree[centroid].clear();

El artículo también menciona una complejidad de actualización de $\mathcal{O}(\log^2n)$ porque asume un factor extra de $\mathcal{O}(\log n)$ para calcular la distancia entre un nodo y un ancestro centroide dado. Sin embargo, podemos precomputar esas distancias (como se muestra en el código de abajo) para reducir la complejidad de actualización a $\mathcal{O}(\log n)$ y la complejidad total a $\mathcal{O}((N + Q)\log n)$ .

Implementación

Más abajo se muestra código general de centroide.

C++Java


vector<vector<int>> adj;
vector<bool> is_removed;
vector<int> subtree_size;
 
/** DFS para calcular el tamaño del subárbol enraizado en `node` */
int get_subtree_size(int node, int parent = -1) {
	subtree_size[node] = 1;
	for (int child : adj[node]) {
		if (child == parent || is_removed[child]) { continue; }
		subtree_size[node] += get_subtree_size(child, node);
	}
	return subtree_size[node];
}
 
/**
 * Devuelve un centroide (un árbol puede tener dos centroides) del subárbol
 * que contiene al nodo `node` después de las remociones de nodos
 * @param node nodo actual
 * @param tree_size tamaño del subárbol actual después de las remociones
 * @param parent padre de u
 * @return primer centroide hallado
 */
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;
}
 
/** Construir la descomposición por centroide de forma recursiva */
void build_centroid_decomp(int node = 0) {
	int centroid = get_centroid(node, get_subtree_size(node));
 
	// hacer algo
 
	is_removed[centroid] = true;
 
	for (int child : adj[centroid]) {
		if (is_removed[child]) { continue; }
		build_centroid_decomp(child);
	}
}


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;
		size = new int[n];
		parent = new int[n];
		seen = new boolean[n];
		initCentroid(0, -1);
	}
 
	private int getSize(int u, int v) {
		if (seen[u]) { return 0; }
		size[u] = 1;
		for (int next : g[u]) {
			if (next != v) { size[u] += getSize(next, u); }
		}
		return size[u];
	}
 
	private void initCentroid(int u, int v) {
		getSize(u, v);
		final int c = findCentroid(u, -1, size[u]);
		seen[c] = true;
		parent[c] = v;
		for (int next : g[c]) {
			if (!seen[next]) { initCentroid(next, c); }
		}
	}
 
	private int findCentroid(int u, int v, int currSize) {
		for (int x : g[u]) {
			if (x != v) {
				if (!seen[x] && size[x] > currSize / 2) {
					return findCentroid(x, u, currSize);
				}
			}
		}
		return u;
	}
}

Solución - Xenia & Tree

Para cada nodo hay a lo sumo $\log N$ componentes de centroide que incluyen a ese nodo, donde $N$ denota la cantidad de nodos. Llamemos ancestro centroide de un nodo al centroide cuya componente contiene a ese nodo. También hay que notar que el camino entre cada par de nodos del árbol debe incluir a uno de sus ancestros centroide comunes, porque el árbol se parte en subárboles con los centroides como raíces respectivas. Si guardamos la distancia al nodo rojo más cercano para cada centroide, podemos consultar la distancia mínima entre cualquier nodo y el nodo rojo más cercano calculando la distancia mínima entre el nodo y uno de sus ancestros centroide más la distancia mínima de ese centroide a un nodo rojo. Para pintar un nodo de rojo, solo actualizamos todos los ancestros centroide de ese nodo. Ambas operaciones se pueden hacer en tiempo $\mathcal{O} (\log N)$ , porque hay a lo sumo esa cantidad de ancestros centroide para un nodo.

C++


#include <bits/stdc++.h>
using namespace std;
 
// un número lo bastante grande sin causar desbordamiento
const int INF = 1e9;
 
vector<vector<int>> adj;
vector<int> subtree_size;
// min_dist[v] := la distancia mínima entre v y un nodo rojo
vector<int> min_dist;
vector<bool> is_removed;
vector<vector<pair<int, int>>> ancestors;
 
int get_subtree_size(int node, int parent = -1) {
	subtree_size[node] = 1;
	for (int child : adj[node]) {
		if (child == parent || is_removed[child]) { continue; }
		subtree_size[node] += get_subtree_size(child, node);
	}
	return subtree_size[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;
}
 
/**
 * Calcular la distancia entre el `node` actual y el `centroid` al que
 * pertenece. Las distancias entre un nodo y todos sus ancestros centroide
 * se guardan en el vector `ancestors`.
 * @param cur_dist la distancia entre `node` y `centroid`
 */
void get_dists(int node, int centroid, int parent = -1, int cur_dist = 1) {
	for (int child : adj[node]) {
		if (child == parent || is_removed[child]) { continue; }
		cur_dist++;
		get_dists(child, centroid, node, cur_dist);
		cur_dist--;
	}
	ancestors[node].push_back({centroid, cur_dist});
}
 
void build_centroid_decomp(int node = 0) {
	int centroid = get_centroid(node, get_subtree_size(node));
 
	/*
	 * Para todos los nodos del subárbol enraizado en `centroid`, calcular
	 * sus distancias al centroide
	 */
	for (int child : adj[centroid]) {
		if (is_removed[child]) { continue; }
		get_dists(child, centroid, centroid);
	}
 
	is_removed[centroid] = true;
	for (int child : adj[centroid]) {
		if (is_removed[child]) { continue; }
		// construir la descomposición por centroide de todas las
		// componentes hijas
		build_centroid_decomp(child);
	}
}
 
/**
 * Pintar `node` de rojo actualizando las distancias mínimas de todos
 * sus ancestros a un nodo rojo
 */
void paint(int node) {
	for (auto &[ancestor, dist] : ancestors[node]) {
		min_dist[ancestor] = min(min_dist[ancestor], dist);
	}
	min_dist[node] = 0;
}
 
/** Imprimir la distancia mínima entre `node` y un nodo rojo */
void query(int node) {
	int ans = min_dist[node];
	for (auto &[ancestor, dist] : ancestors[node]) {
		if (!dist) { continue; }
		/*
		 * La distancia entre `node` y un nodo pintado de rojo es la
		 * suma de la distancia de `node` a uno de sus ancestros
		 * (`dist`) y la distancia de ese ancestro al nodo rojo más
		 * cercano (`min_dist[ancestor]`).
		 */
		ans = min(ans, dist + min_dist[ancestor]);
	}
 
	cout << ans << "\n";
}
 
int main() {
	int N, M;
	cin >> N >> M;
 
	adj.assign(N, vector<int>());
	for (int i = 0; i < N - 1; i++) {
		int a, b;
		cin >> a >> b;
		a--, b--;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
 
	subtree_size.assign(N, 0);
	ancestors.assign(N, vector<pair<int, int>>());
	is_removed.assign(N, false);
	build_centroid_decomp();
 
	min_dist.assign(N, INF);
	paint(0);
	for (int i = 0; i < M; i++) {
		int t, v;
		cin >> t >> v;
		v--;
		if (t == 1) {
			paint(v);
		} else {
			query(v);
		}
	}
}

Problemas

Fuente	Nombre	Dificultad	Tags	Solución
CF	★ Ciel the Commander	Fácil	Centroid	—
Baltic OI	★ 2020 - Village (Maximum)	Fácil	Centroid, Small to Large	—
CSES	★ Fixed-Length Paths I	Fácil	Centroid, Small to Large	Solución
CSES	Fixed-Length Paths II	Fácil	Centroid, BIT	Solución
Old Gold	Yin and Yang	Fácil	Centroid	—
IOI	★ 2011 - Race	Normal	Centroid, Merging	Solución
Platinum	★ New Barns	Normal	Centroid	Solución
CF	Sherlock's bet to Moriarty	Normal	Centroid	—
CF	Digit Tree	Normal	Centroid, NT	—
CF	Double Tree	Normal	Centroid, DP	—
JOI	2014 - Factories	Normal	Centroid	Solución
COCI	2019 - Lampice	Normal	Centroid, Hashing	—
DMOPC	Bob Equilibrium	Difícil	Centroid	Solución
Triway Cup	Time Traveller Imaxblue	Difícil	Centroid	Solución
JOI	2013 - Synchronization	Difícil	Centroid, Small to Large	Solución
Platinum	Cow At Large	Muy difícil	Centroid	Solución