Descomposición por centroide

Conocimiento prerrequisito: Búsqueda en Profundidad (DFS), Divide y vencerás , Árboles .

Introducción

La descomposición por centroide (Centroid Decomposition) es una técnica de divide y vencerás sobre árboles. Se usa para resolver varios problemas que involucran caminos en un árbol, como contar caminos con ciertas propiedades, encontrar distancias o responder consultas sobre caminos del árbol.

La idea clave es descomponer recursivamente un árbol encontrando su centroide. Este vértice especial, al quitarse, parte el árbol en componentes, cada una con a lo sumo la mitad de los vértices del árbol original. Esto garantiza una profundidad logarítmica de la recursión, lo que lleva a algoritmos eficientes.

Propiedades y definición de un centroide

Primero entendamos qué es un centroide. Un centroide de un árbol es un vértice cuya eliminación hace que ningún subárbol tenga más de $\frac{N}{2}$ vértices, donde $N$ es el número total de vértices del árbol.

Para cualquier árbol dado con $N$ vértices, existen uno o dos centroides. Si hay dos centroides, deben, además, ser adyacentes.

Existencia y unicidad

Teorema: Todo árbol tiene al menos un centroide, y a lo sumo dos centroides. Si hay dos centroides, deben ser adyacentes.

Demostración

Existencia: Empezar desde cualquier vértice y seguir moviéndose al hijo con el subárbol más grande. Detenerse cuando ningún hijo tenga más de $\frac{N}{2}$ vértices. En este punto, el vértice actual $v$ es un centroide porque (1) el subárbol de ningún hijo contiene más de $\frac{N}{2}$ vértices (por la condición de parada) (2) el “lado del padre” (todos los vértices excepto el subárbol de $v$ cuando $v$ era un hijo) contiene a lo sumo $\frac{N}{2}$ vértices (de lo contrario no nos habríamos movido a $v$ desde el padre).

Es fácil ver que este proceso siempre termina, lo que prueba que existe al menos un centroide.

Unicidad: Supongamos que hay dos centroides $u$ y $v$ . Consideremos el camino entre ellos. Cuando quitamos $u$ , el vértice $v$ debe estar en una componente con a lo sumo $\frac{N}{2}$ vértices. De forma similar, cuando quitamos $v$ , el vértice $u$ debe estar en una componente con a lo sumo $\frac{N}{2}$ vértices. Esto solo es posible si $u$ y $v$ son adyacentes; de lo contrario, quitar cualquiera de los dos colocaría al otro en una componente con más de $\frac{N}{2}$ vértices. Esto contradice nuestra afirmación inicial de que ambos centroides están en una componente con a lo sumo $\frac{N}{2}$ vértices. Además, si existen dos centroides, deben partir el árbol en dos componentes de exactamente $\frac{N}{2}$ vértices cada una, lo cual solo es posible cuando $N$ es par.

Propiedades y definición de la descomposición por centroide

“Descomponer” el árbol entonces significa esencialmente encontrar centroides de forma recursiva y partir el árbol en subárboles según las componentes del centroide. Tal descomposición recursiva del árbol en sus componentes crea un conjunto único de propiedades:

Profundidad de la descomposición: La profundidad es $O(\log N)$ porque cada nivel al menos reduce a la mitad el tamaño de la componente.
Cobertura de caminos: Todo camino del árbol pasa por el centroide de alguna componente de la descomposición.

Profundidad de la descomposición

Teorema: La profundidad, o número de pasos, al usar descomposición por centroide en cualquier árbol dado es $O(\log N)$ .

Demostración

Consideremos cualquier vértice $v$ del árbol original. Rastreamos cuántas veces $v$ puede ser parte de una componente durante el proceso de descomposición.

En el primer nivel, $v$ está en una componente de tamaño $N$ . Cuando quitamos el centroide de esta componente, $v$ termina en una componente de tamaño a lo sumo $\frac{N}{2}$ (por la propiedad de balance).

En el segundo nivel, $v$ está en una componente de tamaño a lo sumo $\frac{N}{2}$ . Quitar el centroide de esta componente coloca a $v$ en una componente de tamaño a lo sumo $\frac{N}{4}$ .

Continuando este patrón, en el $k$ -ésimo nivel, $v$ está en una componente de tamaño a lo sumo $\frac{N}{2^{k-1}}$ .

La descomposición se detiene cuando los tamaños de las componentes llegan a 1. Esto ocurre cuando $\frac{N}{2^{k-1}} \leq 1$ , lo que nos da $k \leq \log_2 N + 1$ .

Por lo tanto, la profundidad máxima del árbol de descomposición por centroide es $O(\log N)$ .

Consecuencia: Como cada vértice participa en a lo sumo $O(\log N)$ niveles de descomposición, y procesamos cada vértice una vez en cada nivel, los algoritmos que usan descomposición por centroide suelen tener un factor de complejidad temporal de $O(\log N)$ multiplicado por el trabajo hecho por vértice por nivel.

Cobertura de caminos

Teorema: Todo camino del árbol original pasa por el centroide de alguna componente de la descomposición.

Demostración

Consideremos cualquier camino $P$ del vértice $u$ al vértice $v$ en el árbol original. Hay que mostrar que este camino pasa por al menos un centroide elegido durante el proceso de descomposición.

Lo demostramos por inducción sobre el proceso de descomposición.

Caso base: En el primer nivel de descomposición, seleccionamos el centroide $c_1$ de todo el árbol. Si el camino $P$ pasa por $c_1$ , hemos terminado.

Caso inductivo: Supongamos que el camino $P$ no pasa por $c_1$ . Cuando quitamos $c_1$ , el árbol se parte en múltiples componentes. Como $P$ es un camino conexo, tanto $u$ como $v$ deben yacer en la misma componente $C$ después de quitar $c_1$ (de lo contrario, $P$ tendría que pasar por $c_1$ para conectarlos, lo que contradice nuestra hipótesis).

Ahora descomponemos recursivamente la componente $C$ . Por la hipótesis inductiva aplicada a la componente $C$ , el camino $P$ (que está contenido por completo en $C$ ) debe pasar por el centroide de alguna componente en la descomposición de $C$ .

Este proceso continúa hasta que encontramos un centroide por el que pasa $P$ . El proceso debe terminar porque en cada nivel la componente que contiene $P$ se vuelve estrictamente más pequeña (por la propiedad de balance), y eventualmente se reduce a una sola arista o vértice.

Consecuencia: Esta propiedad es fundamental para la corrección de los algoritmos de descomposición por centroide. Asegura que, cuando procesamos todos los caminos a través de cada centroide, cubrimos todos los caminos posibles del árbol exactamente una vez en algún nivel de la descomposición. Por eso la descomposición por centroide puede resolver problemas relacionados con caminos de forma eficiente: cada camino se considera exactamente una vez, en el nivel en el que encuentra por primera vez un centroide.

Encontrar un centroide

Para encontrar un centroide de un árbol de forma eficiente:

Calcular los tamaños de subárbol de todos los vértices usando Búsqueda en Profundidad (DFS)
Empezar desde cualquier vértice
Encontrar un hijo $v$ cuyo subárbol contenga más de $\frac{N}{2}$ vértices
Moverse a $v$ y repetir el paso 3
Si no existe tal hijo, el vértice actual es un centroide

Complejidad temporal: $O(N)$ .

Complejidad espacial: $O(N)$ .

Descripción del algoritmo

Al usar descomposición por centroide, el flujo general funciona de la siguiente forma:

Encontrar el centroide del árbol/componente actual
Procesar todos los caminos que pasan por este centroide y hacer los cálculos deseados
Quitar el centroide (marcarlo como usado)
Descomponer recursivamente cada subárbol resultante

Esto crea un árbol de centroides. Cada nodo de este árbol representa un centroide de alguna etapa de la descomposición. Esto significa que el padre de un centroide (cualquier nodo dado) es el centroide que se encontró en la componente más grande que lo contiene. La altura de este árbol es $O(\log N)$ como se demostró antes.

Por ejemplo, en la imagen de arriba, tenemos un árbol de centroides. Cada nodo en cada nivel del árbol es un centroide de esa componente (p. ej. la raíz es el centroide de todo el árbol, el hijo más a la izquierda de la raíz es el centroide del subárbol más a la izquierda de la raíz, etc.).

Implementación

Aquí hay una implementación de descomposición por centroide que resuelve un problema específico: contar todos los caminos del árbol con longitud exactamente $K$ .

En este problema, nos dan un árbol con $N$ vértices y hay que contar cuántos caminos tienen exactamente $K$ aristas. Un camino se define por dos vértices distintos.


const int MAXN = 1e5;
vector<int> adj[MAXN];
bool removed[MAXN];
int subtree_size[MAXN];
int K;  // Target path length
long long answer = 0;  // Count of paths with length K

int get_subtree_size(int v, int p = -1) {
    subtree_size[v] = 1;
    for (int u : adj[v]) {
        if (u == p || removed[u]) continue;
        subtree_size[v] += get_subtree_size(u, v);
    }
    return subtree_size[v];
}

int get_centroid(int v, int tree_size, int p = -1) {
    for (int u : adj[v]) {
        if (u == p || removed[u]) continue;
        if (subtree_size[u] * 2 > tree_size)
            return get_centroid(u, tree_size, v);
    }
    return v;
}

void get_distances(int v, int p, int dist, vector<int>& distances) {
    if (dist > K) return;
    distances.push_back(dist);
    for (int u : adj[v]) {
        if (u == p || removed[u]) continue;
        get_distances(u, v, dist + 1, distances);
    }
}

void process_centroid(int centroid) {
    unordered_map<int, int> all_distances;
    all_distances[0] = 1;

    for (int u : adj[centroid]) {
        if (removed[u])
            continue;

        vector<int> current_distances;
        get_distances(u, centroid, 1, current_distances);

        for (int d : current_distances) {
            if (K - d >= 0) {
                answer += (all_distances[K - d] ? all_distances[K - d] : 0);
            }
        }

        for (int d : current_distances) {
            if (all_distances.find(d) == all_distances.end())
                all_distances[d] = 0;
            all_distances[d]++;
        }
    }
}

void decompose(int v) {
    int tree_size = get_subtree_size(v);
    int centroid = get_centroid(v, tree_size);

    process_centroid(centroid);

    removed[centroid] = true;

    for (int u : adj[centroid]) {
        if (!removed[u]) {
            decompose(u);
        }
    }
}

Esta plantilla se puede adaptar para resolver distintos problemas usando descomposición por centroide. En este caso específico, resuelve el problema de contar todos los caminos de longitud $K$ . La estrategia es: para cada centroide, contar los caminos que pasan por él encontrando pares de vértices en subárboles distintos a distancias $d_1$ y $d_2$ cuya suma es $K$ (es decir, un camino que pasa por el centroide consiste en un vértice en un subárbol a distancia $d_1$ del centroide y un vértice en otro subárbol a distancia $d_2$ donde $d_1 + d_2 = K$ ). Para cada distancia $d$ en el subárbol actual, el código cuenta cuántos vértices están a distancia $K - d$ en los subárboles anteriores. La optimización salta distancias más allá de $K$ para evitar recursión innecesaria.

Construir el árbol de centroides

Si hay que construir una estructura explícita de árbol de centroides (útil para responder consultas):


int centroid_parent[MAXN];
 
int decompose(int v, int p = -1) {
    int tree_size = get_subtree_size(v);
    int centroid = get_centroid(v, tree_size);
 
    centroid_parent[centroid] = p;
    removed[centroid] = true;
 
    for (int u : adj[centroid]) {
        if (!removed[u]) {
            decompose(u, centroid);
        }
    }
 
    return centroid;
}

Problemas de práctica

CSES - Finding a Centroid [dificultad: fácil]
CSES - Fixed-Length Paths II [dificultad: fácil]
Codeforces - Xenia and Tree [dificultad: media]
Codeforces - Digit Tree [dificultad: media]
OJ - Race [dificultad: media]
SPOJ - QTREE5 [dificultad: difícil]