Descomposición Heavy-Light

La descomposición Heavy-Light (Heavy-Light Decomposition, HLD) es una técnica bastante general que nos permite resolver de forma efectiva muchos problemas que se reducen a consultas sobre un árbol.

Descripción

Sea un árbol $G$ de $n$ vértices, con una raíz arbitraria.

La esencia de esta descomposición del árbol es partir el árbol en varios caminos de modo que podamos alcanzar el vértice raíz desde cualquier $v$ recorriendo a lo sumo $\log n$ caminos. Además, ninguno de estos caminos debe intersectar con otro.

Es claro que si encontramos tal descomposición para cualquier árbol, nos permitirá reducir ciertas consultas individuales de la forma “calcular algo en el camino de $a$ a $b$ ” a varias consultas del tipo ”calcular algo en el segmento $[l, r]$ del $k$ -ésimo camino”.

Algoritmo de construcción

Calculamos para cada vértice $v$ el tamaño de su subárbol $s(v)$ , es decir, el número de vértices en el subárbol del vértice $v$ incluyéndose a sí mismo.

Luego, consideramos todas las aristas que llevan a los hijos de un vértice $v$ . Llamamos a una arista heavy si lleva a un vértice $c$ tal que:

$s(c) \ge \frac{s(v)}{2} \iff \text{edge }(v, c)\text{ is heavy}$

Todas las demás aristas se etiquetan light.

Es obvio que a lo sumo una arista heavy puede salir de un vértice hacia abajo, porque de lo contrario el vértice $v$ tendría al menos dos hijos de tamaño $\ge \frac{s(v)}{2}$ , y por tanto el tamaño del subárbol de $v$ sería demasiado grande, $s(v) \ge 1 + 2 \frac{s(v)}{2} > s(v)$ , lo que lleva a una contradicción.

Ahora descompondremos el árbol en caminos disjuntos. Consideramos todos los vértices de los que no bajan aristas heavy. Subiremos desde cada uno de esos vértices hasta que lleguemos a la raíz del árbol o pasemos por una arista light. Como resultado, obtendremos varios caminos formados por cero o más aristas heavy más una arista light. El camino que tiene un extremo en la raíz es una excepción a esto y no tendrá una arista light. Llamemos a estos caminos heavy: estos son los caminos deseados de la descomposición Heavy-Light.

Demostración de corrección

Primero, notamos que los caminos heavy obtenidos por el algoritmo serán disjuntos. De hecho, si dos de esos caminos tienen una arista en común, implicaría que hay dos aristas heavy que salen de un vértice, lo cual es imposible.

Segundo, mostraremos que al bajar de la raíz del árbol a un vértice arbitrario, cambiaremos no más de $\log n$ caminos heavy por el camino. Bajar por una arista light reduce el tamaño del subárbol actual a la mitad o menos:

$s(c) < \frac{s(v)}{2} \iff \text{edge }(v, c)\text{ is light}$

Así, podemos pasar por a lo sumo $\log n$ aristas light antes de que el tamaño del subárbol se reduzca a uno.

Como solo podemos pasar de un camino heavy a otro a través de una arista light (cada camino heavy, excepto el que empieza en la raíz, tiene una arista light), no podemos cambiar de caminos heavy más de $\log n$ veces a lo largo del camino de la raíz a cualquier vértice, como se requería.

La siguiente imagen ilustra la descomposición de un árbol de ejemplo. Las aristas heavy son más gruesas que las aristas light. Los caminos heavy están marcados por bordes punteados.

Problemas de ejemplo

Al resolver problemas, a veces es más conveniente considerar la descomposición Heavy-Light como un conjunto de caminos disjuntos en vértices (en lugar de caminos disjuntos en aristas). Para ello, basta con excluir la última arista de cada camino heavy si es una arista light; entonces no se violan propiedades, pero ahora cada vértice pertenece a exactamente un camino heavy.

Abajo veremos algunas tareas típicas que se pueden resolver con ayuda de la descomposición Heavy-Light.

Por separado, vale la pena prestar atención al problema de la suma de números en el camino, ya que este es un ejemplo de un problema que se puede resolver con técnicas más simples.

Valor máximo en el camino entre dos vértices

Dado un árbol, a cada vértice se le asigna un valor. Hay consultas de la forma $(a, b)$ , donde $a$ y $b$ son dos vértices del árbol, y se requiere encontrar el valor máximo en el camino entre los vértices $a$ y $b$ .

Construimos de antemano una descomposición Heavy-Light del árbol. Sobre cada camino heavy construiremos un Árbol de Segmentos, que nos permitirá buscar un vértice con el valor asignado máximo en el segmento especificado del camino heavy especificado en $\mathcal{O}(\log n)$ . Aunque el número de caminos heavy en la descomposición Heavy-Light puede alcanzar $n - 1$ , el tamaño total de todos los caminos está acotado por $\mathcal{O}(n)$ , por lo tanto el tamaño total de los Árboles de Segmentos también será lineal.

Para responder una consulta $(a, b)$ , encontramos el ancestro común más bajo de $a$ y $b$ como $l$ , por cualquier método preferido. Ahora la tarea se ha reducido a dos consultas $(a, l)$ y $(b, l)$ , para cada una de las cuales podemos hacer lo siguiente: encontrar el camino heavy en el que yace el vértice inferior, hacer una consulta sobre este camino, movernos a la cima de este camino, otra vez determinar en qué camino heavy estamos y hacer una consulta sobre él, y así sucesivamente, hasta que lleguemos al camino que contiene $l$ .

Hay que tener cuidado con el caso en que, por ejemplo, $a$ y $l$ están en el mismo camino heavy: entonces la consulta de máximo sobre este camino no debe hacerse sobre cualquier prefijo, sino sobre la sección interna entre $a$ y $l$ .

Responder a las subconsultas $(a, l)$ y $(b, l)$ requiere cada una pasar por $\mathcal{O}(\log n)$ caminos heavy y para cada camino se hace una consulta de máximo sobre alguna sección del camino, lo que otra vez requiere $\mathcal{O}(\log n)$ operaciones en el Árbol de Segmentos. Por tanto, una consulta $(a, b)$ toma tiempo $\mathcal{O}(\log^2 n)$ .

Si además se calculan y guardan máximos de todos los prefijos para cada camino heavy, entonces se obtiene una solución $\mathcal{O}(\log n)$ porque todas las consultas de máximo son sobre prefijos excepto a lo sumo una vez cuando llegamos al ancestro $l$ .

Suma de los números en el camino entre dos vértices

Dado un árbol, a cada vértice se le asigna un valor. Hay consultas de la forma $(a, b)$ , donde $a$ y $b$ son dos vértices del árbol, y se requiere encontrar la suma de los valores en el camino entre los vértices $a$ y $b$ . Es posible una variante de esta tarea donde además hay operaciones de actualización que cambian el número asignado a uno o más vértices.

Esta tarea se puede resolver de forma similar al problema anterior de máximos con ayuda de la descomposición Heavy-Light construyendo Árboles de Segmentos sobre caminos heavy. Se pueden usar sumas de prefijos en su lugar si no hay actualizaciones. Sin embargo, este problema también se puede resolver con técnicas más simples.

Si no hay actualizaciones, entonces es posible averiguar la suma en el camino entre dos vértices en paralelo con la búsqueda del LCA de dos vértices por binary lifting: para ello, junto con los ancestros $2^k$ -ésimos de cada vértice también es necesario guardar la suma en los caminos hasta esos ancestros durante el preprocesamiento.

Hay un enfoque fundamentalmente distinto para este problema: considerar el tour de Euler del árbol, y construir un Árbol de Segmentos sobre él. Este algoritmo se considera en un artículo sobre un problema similar. Otra vez, si no hay actualizaciones, guardar sumas de prefijos es suficiente y no se requiere un Árbol de Segmentos.

Ambos de estos métodos dan soluciones relativamente simples que toman $\mathcal{O}(\log n)$ por una consulta.

Repintar las aristas del camino entre dos vértices

Dado un árbol, cada arista está inicialmente pintada de blanco. Hay actualizaciones de la forma $(a, b, c)$ , donde $a$ y $b$ son dos vértices y $c$ es un color, que indica que todas las aristas en el camino de $a$ a $b$ deben repintarse con el color $c$ . Después de todos los repintados, se requiere reportar cuántas aristas de cada color se obtuvieron.

Similar a los problemas de arriba, la solución es simplemente aplicar descomposición Heavy-Light y hacer un Árbol de Segmentos sobre cada camino heavy.

Cada repintado en el camino $(a, b)$ se convertirá en dos actualizaciones $(a, l)$ y $(b, l)$ , donde $l$ es el ancestro común más bajo de los vértices $a$ y $b$ . $\mathcal{O}(\log n)$ por camino para $\mathcal{O}(\log n)$ caminos lleva a una complejidad de $\mathcal{O}(\log^2 n)$ por actualización.

Implementación

Ciertas partes del enfoque discutido arriba se pueden modificar para facilitar la implementación sin perder eficiencia.

La definición de arista heavy se puede cambiar a la arista que lleva al hijo con el subárbol más grande, con empates rotos de forma arbitraria. Esto puede resultar en que algunas aristas light se conviertan en heavy, lo que significa que algunos caminos heavy se combinarán para formar un solo camino, pero todos los caminos heavy seguirán siendo disjuntos. También sigue garantizado que bajar por una arista light reduce el tamaño del subárbol a la mitad o menos.
En lugar de construir un Árbol de Segmentos sobre cada camino heavy, se puede usar un solo Árbol de Segmentos con segmentos disjuntos asignados a cada camino heavy.
Se ha mencionado que responder consultas requiere el cálculo del LCA. Aunque el LCA se puede calcular por separado, también es posible integrar el cálculo del LCA en el proceso de responder consultas.

Para realizar la descomposición Heavy-Light:


vector<int> parent, depth, heavy, head, pos;
int cur_pos;
 
int dfs(int v, vector<vector<int>> const& adj) {
    int size = 1;
    int max_c_size = 0;
    for (int c : adj[v]) {
        if (c != parent[v]) {
            parent[c] = v, depth[c] = depth[v] + 1;
            int c_size = dfs(c, adj);
            size += c_size;
            if (c_size > max_c_size)
                max_c_size = c_size, heavy[v] = c;
        }
    }
    return size;
}
 
void decompose(int v, int h, vector<vector<int>> const& adj) {
    head[v] = h, pos[v] = cur_pos++;
    if (heavy[v] != -1)
        decompose(heavy[v], h, adj);
    for (int c : adj[v]) {
        if (c != parent[v] && c != heavy[v])
            decompose(c, c, adj);
    }
}
 
void init(vector<vector<int>> const& adj) {
    int n = adj.size();
    parent = vector<int>(n);
    depth = vector<int>(n);
    heavy = vector<int>(n, -1);
    head = vector<int>(n);
    pos = vector<int>(n);
    cur_pos = 0;
 
    dfs(0, adj);
    decompose(0, 0, adj);
}

La lista de adyacencia del árbol debe pasarse a la función init, y la descomposición se realiza asumiendo el vértice 0 como raíz.

La función dfs se usa para calcular heavy[v], el hijo en el otro extremo de la arista heavy desde v, para cada vértice v. Además dfs también guarda el padre y la profundidad de cada vértice, lo cual será útil más adelante durante las consultas.

La función decompose asigna para cada vértice v los valores head[v] y pos[v], que son respectivamente la cabeza del camino heavy al que pertenece v y la posición de v en el único Árbol de Segmentos que cubre todos los vértices.

Para responder consultas sobre caminos, por ejemplo la consulta de máximo discutida, podemos hacer algo como esto:


int query(int a, int b) {
    int res = 0;
    for (; head[a] != head[b]; b = parent[head[b]]) {
        if (depth[head[a]] > depth[head[b]])
            swap(a, b);
        int cur_heavy_path_max = segment_tree_query(pos[head[b]], pos[b]);
        res = max(res, cur_heavy_path_max);
    }
    if (depth[a] > depth[b])
        swap(a, b);
    int last_heavy_path_max = segment_tree_query(pos[a], pos[b]);
    res = max(res, last_heavy_path_max);
    return res;
}