Introducción a la Descomposición por Centroides

La descomposición por centroides es una técnica avanzada utilizada para resolver problemas en árboles de manera eficiente, típicamente transformando una complejidad polinomial alta en una más manejable, a menudo logarítmica. Este enfoque es particularmente útil para problemas que implican el conteo o la búsqueda de caminos que satisfacen ciertas propiedades, como la longitud, la suma de pesos, o el número de aristas.

Consideremos un problema clásico: dado un árbol y un entero "k", encontrar el número total de caminos cuya longitud es menor o igual a "k". Las soluciones ingenuas, como enumerar todos los pares de nodos y calcular la distancia (O(N^3) o O(N^2 log N) con LCA), o realizar un DFS desde cada nodo (O(N^2)), resultan ineficientes para árboles grandes. La descomposición por centroides ofrece una alternativa más rápida.

Concepto Fundamental

La idea central de la descomposición por centroides es dividir recursivamente el problema en subproblemas más pequeños. Para un árbol dado, seleccionamos un nodo "p" y clasificamos todos los caminos en dos categorías:

1. Caminos que pasan por el nodo "p" (el "centroide" actual).
2. Caminos que están completamente contenidos dentro de uno de los subárboles formados al eliminar "p".

Los caminos de la primera categoría se pueden calcular directamente para el centroide actual "p". Para los caminos de la segunda categoría, la estrategia es aplicar el mismo algoritmo de forma recursiva a cada uno de los subárboles resultantes. La clave para la eficiencia de esta técnica reside en la elección óptima del nodo "p" en cada paso.

Desglose del Proceso

Un algoritmo de descomposición por centroides sigue estos pasos generales:

1. Selección del Centroide: En la componente actual del árbol que estamos procesando, identificamos su centroide. Un centroide es un nodo que, al ser eliminado, divide el árbol en componentes donde la más grande tiene el menor tamaño posible. Esto garantiza que la profundidad de la recursión sea logarítmica.
2. Cálculo de Caminos que Pasan por el Centroide: Para el centroide "p" seleccionado, se calculan todos los caminos que lo atraviesan y cumplen la condición deseada (por ejemplo, longitud """"k"). Esto generalmente implica realizar un recorrido (DFS) desde "p" para recopilar información sobre las distancias de los nodos a "p" y a qué subárbol pertenecen. Luego se utilizan técnicas como el método de dos punteros sobre la lista de distancias ordenadas.
3. Descomposición Recursiva: Una vez que se han contado los caminos que pasan por "p", "p" se "elimina" lógicamente (se marca como visitado para la descomposición) y el proceso se repite para cada una de las componentes restantes, las cuales son subárboles conectados a "p".

Implementación Detallada

Para calcular los caminos que atraviesan el centroide "p", necesitamos la distancia de cada nodo "x" en la componente actual a "p" (denotada "dist[x]") y el identificador del subárbol "rama[x]" al que pertenece "x" (donde cada rama es un subárbol adjunto a "p" después de su eliminación).

Un camino "x-y" que pasa por "p" tendrá una longitud "dist[x] + dist[y]". Para que este camino sea válido y pase por "p", los nodos "x" y "y" deben pertenecer a ramas diferentes, es decir, "rama[x] != rama[y]".

El algoritmo procesar\_componente(u) puede ser diseñado de la siguiente manera:

1. Marcar u como vistiado: Esto evita que u sea considerado en futuras descomposiciones.
2. Recopilar distancias y subárboles: Realizar un DFS desde u para todos los nodos no visitados en su componente. Para cada nodo v, registrar dist[v] (distancia a u) y rama[v] (la rama a la que v pertenece, definida por el primer vecino de u en el camino a v). Almacenar todos estos nodos en una lista nodos_componente.
3. Ordenar los nodos: Ordenar nodos_componente basándose en sus valores de dist.
4. Contar pares con dos punteros: Utilizar un enfoque de dos punteros (izq y der) en la lista nodos_componente ordenada. Para cada nodos_componente[izq], avanzar der hasta que dist[nodos_componente[izq]] + dist[nodos_componente[der]] <= k. La cantidad de nodos entre izq+1 y der (inclusive) son candidatos.
5. Restar contribuciones del mismo subárbol: Para evitar contar caminos donde rama[x] == rama[y], se mantiene un contador de frecuencias para cada rama. Por cada nodos_componente[izq], la cantidad de caminos válidos es (der - izq) - conteo_ramas[rama[nodos_componente[izq]]]. Esto se debe a que ya hemos procesado el nodo actual y los caminos internos a la misma rama deben ser excluidos.
6. Recursividad en los subárboles: Para cada vecino v de u que no ha sido visitado, se llama recursivamente a procesar_componente(v) después de encontrar el centroide de la componente de v.

Optimización: Uso del Centroide como Punto de División

La eficiencia de la descomposición por centroides radica en una elección óptima del punto de división. Si en cada paso seleccionamos el centroide de la componente actual, garantizamos que el tamaño máximo de cualquier subárbol resultante no exceda la mitad del tamaño de la componente original. Esto reduce la profundidad de la recursión a O(log N). Dado que cada nivel de recursión implica un recorrido (DFS) y una operación de dos punteros que toman O(N) tiempo (donde N es el tamaño de la componente actual), y la ordenación toma O(N log N), la complejidad total se convierte en O(N log^2 N).

Para encontrar el centroide, se realiza un DFS para calcular el tamaño de cada subárbol. El centroide es el nodo que minimiza el tamaño máximo de las componentes resultentes al eliminarlo.

Ejemplo de Código Base (Adaptación para Contar Caminos de Longitud Limitada)

El siguiente código implementa la descomposición por centroides para contar el número de pares de nodos (u, v) tales que la distancia entre ellos sea menor o igual a 'k'.

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

const int MAXN = 40005;

struct Arista {
    int destino;
    int peso;
};

std::vector<Arista> lista_adyacencia[MAXN];
int num_nodos_arbol; // N
int limite_longitud_k; // k

// Variables para encontrar el centroide
int tam_sub_centroide[MAXN]; // Tamano del subarbol para buscar centroide
bool visitado_cd[MAXN];     // Nodos ya procesados por la descomposición
int max_tam_rama_min;       // Minimo del maximo tamano de una rama
int nodo_centroide;         // Nodo que es el centroide

// Variables para calcular distancias desde el centroide
int dist_desde_centroide[MAXN]; // Distancia de nodo a centroide actual
int id_rama_subarbol[MAXN];    // ID del subarbol (rama) al que pertenece el nodo
std::vector<int> nodos_a_procesar; // Nodos en la componente actual para procesar

// Variables para el conteo final
long long conteo_total_caminos;
int conteo_ramas[MAXN]; // Contador de nodos por rama para restar duplicados

// -----------------------------------------------------------------------------
// Funciones de utilidad para la Descomposición por Centroides
// -----------------------------------------------------------------------------

// Paso 1: Buscar el centroide
void dfs_tamano_subarbol(int u, int padre, int& tamano_comp_actual) {
    tam_sub_centroide[u] = 1;
    max_tam_rama_min = std::max(max_tam_rama_min, tamano_comp_actual - tam_sub_centroide[u]);
    for (const auto& arista : lista_adyacencia[u]) {
        int v = arista.destino;
        if (v == padre || visitado_cd[v]) continue;
        dfs_tamano_subarbol(v, u, tamano_comp_actual);
        tam_sub_centroide[u] += tam_sub_centroide[v];
        max_tam_rama_min = std::max(max_tam_rama_min, tam_sub_centroide[v]);
    }
}

void buscar_centroide_recursivo(int u, int padre, int tamano_comp_actual) {
    int max_rama_actual = tamano_comp_actual - tam_sub_centroide[u];
    for (const auto& arista : lista_adyacencia[u]) {
        int v = arista.destino;
        if (v == padre || visitado_cd[v]) continue;
        max_rama_actual = std::max(max_rama_actual, tam_sub_centroide[v]);
    }

    if (max_rama_actual < max_tam_rama_min) {
        max_tam_rama_min = max_rama_actual;
        nodo_centroide = u;
    }

    for (const auto& arista : lista_adyacencia[u]) {
        int v = arista.destino;
        if (v == padre || visitado_cd[v]) continue;
        buscar_centroide_recursivo(v, u, tamano_comp_actual);
    }
}

// Paso 2: Recopilar distancias desde el centroide y asignar ramas
void explorar_componente_distancias(int u, int padre, int dist_actual, int id_rama) {
    dist_desde_centroide[u] = dist_actual;
    id_rama_subarbol[u] = id_rama;
    nodos_a_procesar.push_back(u);

    for (const auto& arista : lista_adyacencia[u]) {
        int v = arista.destino;
        if (v == padre || visitado_cd[v]) continue;
        explorar_componente_distancias(v, u, dist_actual + arista.peso, id_rama);
    }
}

// -----------------------------------------------------------------------------
// Lógica principal de Descomposición por Centroides
// -----------------------------------------------------------------------------

// Calcula los caminos que pasan por el centroide actual
long long calcular_caminos_atravesando_centroide(int centroide_actual) {
    long long caminos_encontrados = 0;
    nodos_a_procesar.clear(); // Limpiar nodos para la nueva componente
    
    // El centroide se considera parte de su propia rama, con distancia 0
    dist_desde_centroide[centroide_actual] = 0;
    id_rama_subarbol[centroide_actual] = centroide_actual; // Usamos el ID del propio nodo para la rama "central"
    nodos_a_procesar.push_back(centroide_actual);

    // Explorar los subárboles (ramas) adyacentes al centroide
    for (const auto& arista : lista_adyacencia[centroide_actual]) {
        int v = arista.destino;
        if (visitado_cd[v]) continue;
        explorar_componente_distancias(v, centroide_actual, arista.peso, v); // v es el identificador de la rama
    }

    // Ordenar nodos por distancia desde el centroide
    std::sort(nodos_a_procesar.begin(), nodos_a_procesar.end(), 
              [&](int a, int b) { return dist_desde_centroide[a] < dist_desde_centroide[b]; });

    // Contar caminos usando dos punteros y el array de conteo_ramas
    int izq = 0, der = nodos_a_procesar.size() - 1;
    for (int i = 0; i < nodos_a_procesar.size(); ++i) {
        conteo_ramas[id_rama_subarbol[nodos_a_procesar[i]]]++;
    }

    while (izq < der) {
        if (dist_desde_centroide[nodos_a_procesar[izq]] + dist_desde_centroide[nodos_a_procesar[der]] <= limite_longitud_k) {
            // Contar todos los nodos 'der' que son válidos con 'izq'
            // y restar los que están en la misma rama que 'izq'
            caminos_encontrados += (der - izq) - conteo_ramas[id_rama_subarbol[nodos_a_procesar[izq]]] + 1; // +1 porque el centroide es una rama especial
            izq++;
        } else {
            der--;
        }
    }

    // Limpiar conteo_ramas para la próxima llamada o componente
    for (int nodo : nodos_a_procesar) {
        conteo_ramas[id_rama_subarbol[nodo]] = 0;
    }

    return caminos_encontrados;
}


// Función principal de la Descomposición por Centroides
void descomponer_arbol(int u) {
    // Encontrar el centroide de la componente actual
    max_tam_rama_min = INT_MAX;
    dfs_tamano_subarbol(u, 0, u); // Calculamos tamaños para toda la componente
    buscar_centroide_recursivo(u, 0, tam_sub_centroide[u]); // u ahora representa el tamaño total de la componente

    int centroide = nodo_centroide;
    visitado_cd[centroide] = true; // Marcar el centroide como visitado para la descomposición

    // Calcular caminos que pasan por este centroide y sumarlos al total
    conteo_total_caminos += calcular_caminos_atravesando_centroide(centroide);

    // Recursivamente descomponer los subárboles adyacentes al centroide
    for (const auto& arista : lista_adyacencia[centroide]) {
        int v = arista.destino;
        if (!visitado_cd[v]) {
            descomponer_arbol(v); // Llamada recursiva con el vecino
        }
    }
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    std::cin >> num_nodos_arbol;
    for (int i = 0; i < num_nodos_arbol - 1; ++i) {
        int u, v, w;
        std::cin >> u >> v >> w;
        lista_adyacencia[u].push_back({v, w});
        lista_adyacencia[v].push_back({u, w});
    }
    std::cin >> limite_longitud_k;

    descomponer_arbol(1); // Empezar la descomposición desde un nodo arbitrario (e.g., nodo 1)

    std::cout << conteo_total_caminos << std::endl;

    return 0;
}

Aplicaciones y Variaciones

1. Conteo de Caminos con Longitud Máxima (Problema P4178)

Esta es la aplicación estándar de la descomposición por centroides, como se detalla en la sección anterior. El código de ejemplo provisto resuelve directamente este tipo de problema, contando la cantidad de pares de nodos cuya distancia es "k" o menos.

2. Verificación de Existencia de Caminos con Longitudes Específicas (Problema P3806)

En lugar de contar, a veces se nos pide verificar si existen caminos de longitudes específicas dentro de un árbol. La estructura general de la descomposición por centroides permanece, pero la función de "cálculo" cambia. En vez de sumar a un contador, se actualiza un arreglo booleano "existe_camino[longitud]". Al usar el método de dos punteros, se buscan pares "(x,y)" tales que "dist[x] + dist[y] = L" para cada "L" de las longitudes objetivo, asegurándose de que "rama[x] != rama[y]".

// fragmento de la funcion "procesar_componente_centroide" para P3806
// ... (parte de recopilacion de distancias y ramas es similar)

    // Despues de ordenar nodos_a_procesar por dist_desde_centroide
    // ...
    
    // `queries_longitudes` es un vector de las longitudes que queremos verificar.
    // `respuestas_query[L]` es true si existe un camino de longitud L.
    
    // Usamos un 'hash table' o un array de frecuencia para almacenar distancias
    std::vector<bool> distancias_encontradas_temp(limite_max_query + 1, false);
    distancias_encontradas_temp[0] = true; // El centroide tiene distancia 0 a si mismo

    for (int i = 1; i < nodos_a_procesar.size(); ++i) {
        int u = nodos_a_procesar[i];
        if (id_rama_subarbol[u] == centroide_actual) continue; // Si es el centroide, ya lo hemos considerado
        
        for (int query_len : queries_longitudes) { // Iterar sobre cada longitud de consulta
            if (query_len - dist_desde_centroide[u] >= 0 && 
                query_len - dist_desde_centroide[u] <= limite_max_query) {
                if (distancias_encontradas_temp[query_len - dist_desde_centroide[u]]) {
                    respuestas_query[query_len] = true;
                }
            }
        }
        distancias_encontradas_temp[dist_desde_centroide[u]] = true; // Añadir la distancia actual
    }

    // Para evitar caminos dentro de la misma rama, se pueden procesar las ramas una a una
    // y usar un contenedor temporal para las distancias, vaciandolo y reconstruyendolo
    // para cada rama, o usar el truco de dos punteros con `id_rama_subarbol`.

    // El enfoque con dos punteros seria:
    // int izq = 0, der = nodos_a_procesar.size() - 1;
    // while (izq < der) {
    //     int current_sum = dist_desde_centroide[nodos_a_procesar[izq]] + dist_desde_centroide[nodos_a_procesar[der]];
    //     // Verificar si current_sum es una de las queries_longitudes y rama[izq] != rama[der]
    //     // ...
    //     if (current_sum > max_query_length) der--;
    //     else if (current_sum < min_query_length) izq++;
    //     else { // current_sum podria ser una respuesta
    //         // Buscar current_sum en queries_longitudes y verificar ramas
    //         if (id_rama_subarbol[nodos_a_procesar[izq]] != id_rama_subarbol[nodos_a_procesar[der]]) {
    //             // Marcar como respondido si coincide con una query
    //         }
    //         // Ajustar punteros, con cuidado si hay elementos iguales o varias queries
    //         // Esto puede ser mas complejo si hay multiples queries o elementos iguales
    //     }
    // }

// ... (parte recursiva es similar)

Un detalle importante es que las consultas deben ser gestionadas dentro de la función recursiva. Iterar sobre todas las consultas en cada paso del proceso (o dentro del bucle de dos punteros) es crucial para la eficiencia.

3. Camino Más Corto con Longitud Específica (Problema P4149)

Aquí, el objetivo es encontrar el camino con la menor cantidad de aristas (o nodos) que tenga una longitud total específica "k". Además de la distancia al centroide ("dist[x]"), también necesitamos registrar la profundidad o el número de aristas desde el centroide ("prof[x]"). Al usar el método de dos punteros, cuando encontramos un par "(x,y)" tal que "dist[x] + dist[y] == k" y "rama[x] != rama[y]", actualizamos la respuesta global con "min(respuesta, prof[x] + prof[y])".

// fragmento de la funcion "procesar_componente_centroide" para P4149
// ... (parte de encontrar centroide es similar)

// Variables adicionales para este problema:
int profundidad_desde_centroide[MAXN]; // Numero de aristas desde el centroide

// Modificar explorar_componente_distancias para capturar profundidad:
void explorar_componente_distancias_con_prof(int u, int padre, int dist_actual, int prof_actual, int id_rama) {
    dist_desde_centroide[u] = dist_actual;
    profundidad_desde_centroide[u] = prof_actual;
    id_rama_subarbol[u] = id_rama;
    nodos_a_procesar.push_back(u);

    for (const auto& arista : lista_adyacencia[u]) {
        int v = arista.destino;
        if (v == padre || visitado_cd[v]) continue;
        explorar_componente_distancias_con_prof(v, u, dist_actual + arista.peso, prof_actual + 1, id_rama);
    }
}

// ...
// Dentro de la función que calcula caminos para el centroide:
// Antes del sort:
// El centroide tiene distancia 0 y profundidad 0 a si mismo
dist_desde_centroide[centroide_actual] = 0;
profundidad_desde_centroide[centroide_actual] = 0;
id_rama_subarbol[centroide_actual] = centroide_actual;
nodos_a_procesar.push_back(centroide_actual);

// Para las ramas:
for (const auto& arista : lista_adyacencia[centroide_actual]) {
    int v = arista.destino;
    if (visitado_cd[v]) continue;
    explorar_componente_distancias_con_prof(v, centroide_actual, arista.peso, 1, v);
}

// ... (Ordenar nodos_a_procesar por dist_desde_centroide)

int min_caminos_longitud_k = INT_MAX;
// Usar un array de frecuencia para las distancias (ej. `min_prof_por_distancia[distancia] = prof`)
std::vector<int> min_prof_por_distancia(limite_longitud_k + 1, INT_MAX);
min_prof_por_distancia[0] = 0; // Para la distancia 0 (el centroide)

for (int nodo_idx : nodos_a_procesar) { // Iterar sobre todos los nodos de la componente
    int d_u = dist_desde_centroide[nodo_idx];
    int p_u = profundidad_desde_centroide[nodo_idx];
    
    if (d_u == 0) continue; // El centroide ya está manejado

    // Encontrar si existe una distancia complementaria para formar K
    if (limite_longitud_k - d_u >= 0 && 
        limite_longitud_k - d_u <= limite_longitud_k) {
        
        // Verificar todas las distancias "restantes" posibles
        // Para esto se podria usar un mapa o un array para buscar eficientemente
        // las distancias ya procesadas y sus profundidades minimas
        // Si (d_v = k - d_u) existe y rama[u] != rama[v], actualizar min_caminos_longitud_k
        // Un enfoque más simple para evitar el problema de rama:
        // Procesar nodo por nodo, y antes de agregar la distancia actual al `min_prof_por_distancia`
        // revisar si forma un camino valido con las distancias ya agregadas.
        
        // El truco es que necesitamos una tabla auxiliar `temp_min_prof_por_distancia` 
        // para solo contar caminos de ramas diferentes.
        // O un enfoque de dos punteros con `min_prof_por_distancia` para cada rama
    }
}

// Reimplementación del conteo usando un map temporal y dos punteros
std::map<int, int> dist_to_min_prof;
dist_to_min_prof[0] = 0; // El centroide
min_prof_por_distancia[0] = 0;

for (int i = 1; i < nodos_a_procesar.size(); ++i) {
    int u = nodos_a_procesar[i];
    int d_u = dist_desde_centroide[u];
    int p_u = profundidad_desde_centroide[u];

    if (limite_longitud_k - d_u >= 0) {
        if (min_prof_por_distancia[limite_longitud_k - d_u] != INT_MAX) {
            if (id_rama_subarbol[u] != id_rama_subarbol[min_prof_por_distancia[limite_longitud_k - d_u]]) { // Esto es incorrecto, no almacena id_rama_subarbol
                // Se necesita una forma de saber el id_rama_subarbol para la distancia complementaria
                // Un enfoque comun es procesar una rama a la vez, y para cada rama, usar un mapa temporal
                // para las distancias/profundidades de esa rama, y compararlo con el mapa global
                // que contiene las distancias/profundidades de las ramas previamente procesadas.
            }
        }
    }
    
    // Actualizar min_prof_por_distancia global
    // Este `min_prof_por_distancia` debería ser solo para las ramas ya procesadas
    // y para la rama actual se usa un map local
    // min_prof_por_distancia[d_u] = std::min(min_prof_por_distancia[d_u], p_u);
}
// ...

La implementación de P4149 es más compleja porque requiere no solo la existencia de la distancia, sino también minimizar la profundidad, y aún así evitar caminos en la misma rama. Esto a menudo se resuelve iterando sobre las ramas adyacentes al centroide, procesando una a una: para cada rama, se usa una tabla auxiliar para sus distancias/profundidades y luego se compara con una tabla global que contiene las distancias/profundidades de las ramas ya procesadas.