Heavy-light decomposition

Heavy-light decomposition é uma técnica generalizada que nos permite resolver efetivamente muitos problemas que se resumem a consultas (queries) em uma árvore.

Descrição

Seja $G$ uma árvore de $n$ vértices, com uma raiz arbitrária.

A essência dessa decomposição na árvore é dividir a árvore em vários caminhos para que possamos alcançar o vértice raiz de qualquer $v$ percorrendo no máximo $\log n$ caminhos. Além disso, nenhum desses caminhos devem sofrer interseções uns com os outros.

É claro que se encontrarmos essa decomposição para qualquer árvore, ela nos permitirá reduzir determinadas consultas únicas da forma: “calcular algo no caminho de $a$ a $b$” para várias consultas do tipo ”calcular algo no segmento $[l;r]$ do $k^{ésimo}$ caminho”.

Construção do algoritmo

Calculamos para cada vértice $v$ o tamanho de sua subárvore $s(v)$, ou seja, o número de vértices na subárvore do vértice $v$ incluindo ele mesmo.

Em seguida, considere todas as arestas que levam aos filhos de um vértice $v$. Dizemos que uma aresta é "heavy" se levar a um vértice $c$ de modo que:

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

Todas as outras arestas são definidas como "light".

No máximo uma aresta heavy pode vir de um vértice de baixo, pois caso contrário o vértice $v$ teria pelo menos dois filhos de tamanho $\ge \frac{s(v)}{2}$, e, portanto, o tamanho da subárvore de $v$ seria muito grande, $s(v) \ge 1 + 2 \frac{s(v)}{2} > s(v)$, o que leva a uma contradição.

Agora vamos decompor a árvore em caminhos disjuntos. Considere todos os vértices dos quais nenhuma aresta heavy venha de baixo. Subiremos de cada um desses vértices até chegarmos à raiz da árvore ou atravessaremos uma aresta light. Como resultado, obteremos vários caminhos compostos por zeros ou mais arestas heavy adicionados. O caminho que tem um fim na raiz é uma exceção e não terá uma aresta leve(light). Esses serão chamados de heavy paths - esses são os caminhos desejados da heavy-light decomposition.

Prova

Primeiro, observamos que os "heavy paths" obtidos pelo algoritmo serão disjuntos. De fato, se dois desses caminhos têm uma aresta comum, isso implica que há duas arestas "heavy" saindo de um vértice, o que é impossível.

Em segundo lugar, mostraremos que, descendo da raiz da árvore para um vértice arbitrário, mudaremos não mais que $\log n$ "heavy paths" ao longo do caminho. Mover para baixo uma light edge reduz o tamanho da subárvore atual na metade ou até menor que isso:

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

Assim, podemos percorrer no máximo $\log n$ light edges antes que o tamanho da subárvore se reduza a um.

Como podemos passar de um heavy path para outro apenas por uma light edge (cada heavy path, exceto o que começa na raiz, tem uma light edge), não podemos alterar os heavy paths mais do que $\log n$ vezes ao longo do caminho da raiz para qualquer vértice.

A imagem a seguir ilustra a decomposição de uma árvore de amostra. As heavy edges("arestas pesadas": vamos definir dessa maneira aqui) são mais espessas do que as light edges("arestas leves/finas"). Os heavy paths("caminhos pesados") são marcados por limites pontilhados.

Image of HLD

Problemas

Ao resolver problemas, as vezes é mais conveniente considerar a heavy-light decomposition como um conjunto de caminhos de vértices disjuntos (em vez de caminhos de arestas disjuntas). Para fazer isso, basta excluir a última aresta de cada heavy path, se for uma light edge - nenhuma propriedade será violada; agora cada vértice pertence exatamente a um heavy path.

Abaixo, veremos algumas tarefas típicas que podem ser resolvidas com a ajuda da heavy-light decomposition.

Separadamente, vale a pena prestar atenção ao problema da soma dos números em um caminho, pois esse é um exemplo de um problema que pode ser resolvido por técnicas mais simples.

Valor máximo no caminho entre dois vértices

Dada uma árvore, cada vértice recebe um valor. Existem consultas da forma $(a, b)$, em que $a$ e $b$ são dois vértices na árvore e é necessário encontrar o valor máximo no caminho entre os vértices $a$ e $b$.

Construímos antecipadamente uma heavy-light decomposition da árvore. Sobre cada heavy path construiremos uma árvore segmentária, que permitirá procurar um vértice com o valor máximo atribuído no segmento especificado do específico heavy path, em $\mathcal{O}(\log n)$. Embora o número de heavy paths na heavy-light decomposition possa alcançar $n - 1$, o tamanho total de todos os caminhos é limitado por $\mathcal{O}(n)$, portanto, o tamanho total das árvores de segmento também será linear.

Para responder a uma consulta $(a, b)$, encontramos o menor ancestral comum de $a$ e $b$, definido como $l$, por qualquer método preferido. Agora a tarefa foi reduzida para duas consultas $(a, l)$ e $(b, l)$, para cada uma das quais podemos fazer o seguinte: encontrar o heavy path em que o vértice inferior se encontra, faça uma consulta nesse caminho, vá para o topo desse caminho, determine novamente em que heavy path estamos e faça uma consulta nele, e assim por diante, até chegarmos ao caminho que contém $l$.

Deve-se ter cuidado com o caso quando, por exemplo, $a$ e $l$ estiverem no mesmo heavy path - a consulta máxima nesse caminho deve ser feita não em nenhum prefixo, mas na seção interna entre $a$ e $l$.

Para responder às subconsultas $(a, l)$ e $(b, l)$ cada uma requer percorrer por $\mathcal{O}(\log n)$ heavy paths e, para cada caminho, é feita uma consulta máxima em alguma seção de o caminho, que novamente requer $\mathcal{O}(\log n)$ operações na árvore de segmentos. Portanto, uma consulta $(a, b)$ leva tempo $\mathcal{O}(\log^2 n)$.

Se você calcular e armazenar adicionalmente o máximo de todos os prefixos para cada heavy path, então teremos uma solução $\mathcal{O}(\log n)$ porque todas as consultas máximas estarão nos prefixos, exceto quando atingirmos o ancestral $l$.

Soma dos números no caminho entre dois vértices

Dada uma árvore, cada vértice recebe um valor. Existem consultas da forma $(a, b)$, em que $a$ e $b$ são dois vértices na árvore e é necessário encontrar a soma dos valores no caminho entre os vértices $a$ e $b$. É possível uma variante dessa tarefa, onde adicionalmente existem operações de atualização que alteram o número atribuído a um ou mais vértices(veja "árvore segmentária" e problemas relacionados).

Essa tarefa pode ser resolvida de maneira semelhante ao problema anterior de máximos, com a ajuda da heavy-light decomposition by construindo árvores de segmentos em heavy paths. Em vez disso, somas de prefixo podem ser usadas se não houver atualizações. No entanto, esse problema também pode ser resolvido por técnicas mais simples.

Se não houver atualizações, é possível descobrir a soma no caminho entre dois vértices em paralelo com a pesquisa do LCA de dois vértices por binary lifting — para isso, juntamente com os $2^k$-ésimos ancestrais de cada vértice também é necessário armazenar a soma nos caminhos até esses ancestrais durante o pré-processamento.

Existe uma abordagem fundamentalmente diferente para esse problema - considerando o tour de Euler pela árvore e criando uma árvore de segmentos nele. Esse algoritmo é considerado em um artigo com um problema semelhante. Novamente, se não houver atualizações, armazenar somas de prefixos é suficiente e uma árvore segmentária não é necessária.

Ambos os métodos fornecem soluções relativamente simples, levando $\mathcal{O}(\log n)$ para uma consulta.

Recolorir as arestas de um caminho entre dois vértices

Dada uma árvore, cada aresta é inicialmente colorida em branco. Existem atualizações da forma $(a, b, c)$, em que $a$ e $b$ são dois vértices e $c$ é uma cor, o que instrui que todas as arestas no caminho de $a$ a $b$ devem ser recoloridas com a cor $c$. Após todas as recolorações, é necessário relatar quantas arestas de cada cor foram obtidas.

Semelhante aos problemas acima, a solução é simplesmente aplicar uma heavy-light decomposition e criar uma árvore segmentária sobre cada heavy path.

Cada recoloração no caminho $(a, b)$ se transformará em duas atualizações $(a, l)$ e $(b, l)$, em que $l$ é o menor ancestral comum dos vértices $a$ e $b$.
$\mathcal{O}(\log n)$ por caminho para $\mathcal{O}(\log n)$ caminhos, leva a uma complexidade de $\mathcal{O}(\log^2 n)$ por atualização.

Implementação

Certas partes da abordagem discutida acima podem ser modificadas para facilitar a implementação sem perder a eficiência.

Para performar uma heavy-light decomposition:

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;
}

int 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);
}

A lista de adjacência da árvore deve ser passada para a função init, e a decomposição é realizada assumindo o vértice 0 como raiz.

A função dfs é usada para calcular heavy[v], o vértice filho do outro lado final da heavy edge de v, para cada vértice v. Adicionalmente, a dfs também armazena o parente e a profundidade de cada vértice, o que será útil posteriormente durante as consultas.

A função decompose atribui para cada vértice v os valores head[v] e pos[v], que são, respectivamente, a frente do heavy path v e a posição de v na árvore de segmentos única que cobre todos os vértices.

Para responder consultas sobre caminhos, por exemplo, a consulta máxima discutida, podemos fazer algo assim:

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;
}