Conceptos Fundamentales

La descomposición en cadenas pesadas (Heavy-Light Decomposition) es una técnica para particionar árboles en estructuras lineales que permiten resolver operaciones compeljas eficientemente. Se basa en clasificar nodos y aristas según el tamaño de sus subárboles:

• Nodo pesado: Hijo con el subárbol más grande. En caso de empate, se selecciona uno arbitrariamente.
• Nodo ligero: Cualquier hijo que no sea el nodo pesado.
• Arista pesada: Conexión entre un nodo y su nodo pesado.
• Arista ligera: Conexión entre un nodo y sus nodos ligeros.
• Cadena pesada: Secuencia contigua de aristas pesadas.

Esta partición garantiza que cualquier camino desde la raíz hasta una hoja atraviesa como máximo log₂(n) aristas ligeras, lo que permite optimizar operaciones.

Implementación Detallada

Se requieren dos recorridos DFS para preprocesar la información esencial. Primero definimos la estructura del nodo:

struct Vertice {
    int padre, profundidad, tamSubarbol, hijoPesado, topeCadena;
    int indiceDFS, posicionOriginal;
};

Primer recorrido para calcular tamaños de subárboles y nodos pesados:

void preprocesarSubarboles(int nodoActual, int nivel) {
    vertices[nodoActual].profundidad = nivel;
    vertices[nodoActual].tamSubarbol = 1;
    vertices[nodoActual].hijoPesado = -1;
    
    for (int vecino : grafo[nodoActual]) {
        if (vecino == vertices[nodoActual].padre) continue;
        
        vertices[vecino].padre = nodoActual;
        preprocesarSubarboles(vecino, nivel + 1);
        vertices[nodoActual].tamSubarbol += vertices[vecino].tamSubarbol;
        
        if (vertices[nodoActual].hijoPesado == -1 || 
            vertices[vecino].tamSubarbol > vertices[vertices[nodoActual].hijoPesado].tamSubarbol) {
            vertices[nodoActual].hijoPesado = vecino;
        }
    }
}

Segundo recorrido para establecer cadenas y numeración DFS:

int contadorDFS = 0;
void construirCadenas(int nodoActual, int topeActual) {
    vertices[nodoActual].topeCadena = topeActual;
    vertices[nodoActual].indiceDFS = ++contadorDFS;
    posicionDFS[contadorDFS] = nodoActual;
    
    if (vertices[nodoActual].hijoPesado != -1) {
        construirCadenas(vertices[nodoActual].hijoPesado, topeActual);
    }
    
    for (int vecino : grafo[nodoActual]) {
        if (vecino != vertices[nodoActual].padre && vecino != vertices[nodoActual].hijoPesado) {
            construirCadenas(vecino, vecino);
        }
    }
}

Aplicaciones Clave

Esta estructura habilita tres operaciones fundamentales en tiempo logarítmico:

Suma en Caminos entre Nodos

Para calculra la suma entre dos nodos u y v:

long long calcularSumaCamino(int u, int v) {
    long long resultado = 0;
    while (vertices[u].topeCadena != vertices[v].topeCadena) {
        if (vertices[vertices[u].topeCadena].profundidad < vertices[vertices[v].topeCadena].profundidad) 
            swap(u, v);
        resultado += consultaSegmento(vertices[vertices[u].topeCadena].indiceDFS, 
                                    vertices[u].indiceDFS);
        u = vertices[vertices[u].topeCadena].padre;
    }
    if (vertices[u].profundidad > vertices[v].profundidad) swap(u, v);
    return resultado + consultaSegmento(vertices[u].indiceDFS, vertices[v].indiceDFS);
}

Actualización de Subárboles

Para modificar todos los nodos en el subárbol de x:

void actualizarSubarbol(int x, long long valor) {
    int inicio = vertices[x].indiceDFS;
    int fin = inicio + vertices[x].tamSubarbol - 1;
    actualizarSegmento(inicio, fin, valor);
}

Cálculo de LCA Eficiente

El ancestro común más bajo se obtiene mediante saltos entre cadenas:

int encontrarLCA(int u, int v) {
    while (vertices[u].topeCadena != vertices[v].topeCadena) {
        if (vertices[vertices[u].topeCadena].profundidad < vertices[vertices[v].topeCadena].profundidad)
            v = vertices[vertices[v].topeCadena].padre;
        else
            u = vertices[vertices[u].topeCadena].padre;
    }
    return vertices[u].profundidad < vertices[v].profundidad ? u : v;
}