A Decomposição em Cadeias Pesadas e Leves (Heavy-Light Decomposition - HLD) é uma técnica avançada utilizada para transformar a estrutura hierárquica de uma árvore em um conjunto de sequências linaeres. Essa linearização permite a aplicação de estruturas de dados de intervalos, como a Árvore de Segmentos (Segment Tree), para realizar consultas e atualizações eficientes em caminhos ou subárvores.
Terminologia Fundamental
Para compreender o algoritmo, é necessário dominar os seguintes conceitos:
- Filho Pesado (Heavy Child): O nó filho que possui a maior subárvore em termos de quantidade de nós.
- Filho Leve (Light Child): Qualquer nó filho que não seja o filho pesado.
- Aresta Pesada (Heavy Edge): A aresta que conecta um nó ao seu filho pesado.
- Aresta Leve (Light Edge): Qualquer aresta que conecte um nó a um filho leve.
- Cadeia Pesada (Heavy Chain): Um caminho contínuo formado exclusivamente por arestas pesadas.
- Cadeia Leve (Light Chain): Um caminho formado por arestas leves.
Propriedades Estruturais
A decomposição garante características cruciais para a complexidade do algoritmo:
- Cada nó da árvore pertence a exatamente uma cadeia pesada.
- Os nós de qualquer subárvore ocupam posições contíguas após a reindexação.
- Os nós de uma mesma cadeia pesada possuem índices contíguos.
- O tamanho da subárvore de qualquer filho leve é, no máximo, a metade do tamanho da subárvore de seu pai.
- O caminho entre a raiz e qualquer nó cruza no máximo O(log N) cadeias pesadas.
Etapas do Algoritmo
O processo de decomposição é dividido em duas passagens de Busca em Profuniddade (DFS).
1. Primeira DFS: Cálculo de Métricas
Nesta etapa, calculamos a profundidade, o tamanho da subárvore, o pai e identificamos o filho pesado de cada nó.
vector<int> adj[MAX_NODES];
int depth[MAX_NODES], subtree_size[MAX_NODES];
int heavy_child[MAX_NODES], parent_node[MAX_NODES];
void compute_metrics(int u, int p, int d) {
parent_node[u] = p;
depth[u] = d;
subtree_size[u] = 1;
heavy_child[u] = -1;
int max_sub_size = 0;
for (int v : adj[u]) {
if (v != p) {
compute_metrics(v, u, d + 1);
subtree_size[u] += subtree_size[v];
if (subtree_size[v] > max_sub_size) {
max_sub_size = subtree_size[v];
heavy_child[u] = v;
}
}
}
}
2. Segunda DFS: Linearização e Mapeamento
Aqui, priorizamos a visita ao filho pesado para garantir que os nós da mesma cadeia recebam índices contíguos. Também registramos o topo (cabeça) de cada cadeia.
int pos_in_array[MAX_NODES], chain_head[MAX_NODES];
int current_pos = 0;
long long mapped_values[MAX_NODES], initial_values[MAX_NODES];
void decompose(int u, int head) {
chain_head[u] = head;
pos_in_array[u] = ++current_pos;
mapped_values[current_pos] = initial_values[u];
if (heavy_child[u] != -1) {
decompose(heavy_child[u], head);
}
for (int v : adj[u]) {
if (v != parent_node[u] && v != heavy_child[u]) {
decompose(v, v);
}
}
}
3. Integração com Árvore de Segmentos
Com os nós mapeados em um array linear, construímos uma Árvore de Segmentos com propagação preguiçosa (lazy propagation) para suportar atualizações de soma em intervalos e consultas de soma.
Implementação Completa
Abaixo está a implementação completa em C++, incluindo a estrutura de grafo, a decomposição e a árvore de segmentos para operações de soma e atualização em caminhos e subárvores.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int MAX_NODES = 100005;
int total_nodes, total_queries, root_node;
long long modulo;
vector<int> adj[MAX_NODES];
long long initial_values[MAX_NODES];
int depth[MAX_NODES], subtree_size[MAX_NODES];
int heavy_child[MAX_NODES], parent_node[MAX_NODES];
int pos_in_array[MAX_NODES], chain_head[MAX_NODES];
int current_pos = 0;
long long mapped_values[MAX_NODES];
void compute_metrics(int u, int p, int d) {
parent_node[u] = p;
depth[u] = d;
subtree_size[u] = 1;
heavy_child[u] = -1;
int max_sub_size = 0;
for (int v : adj[u]) {
if (v != p) {
compute_metrics(v, u, d + 1);
subtree_size[u] += subtree_size[v];
if (subtree_size[v] > max_sub_size) {
max_sub_size = subtree_size[v];
heavy_child[u] = v;
}
}
}
}
void decompose(int u, int head) {
chain_head[u] = head;
pos_in_array[u] = ++current_pos;
mapped_values[current_pos] = initial_values[u];
if (heavy_child[u] != -1) {
decompose(heavy_child[u], head);
}
for (int v : adj[u]) {
if (v != parent_node[u] && v != heavy_child[u]) {
decompose(v, v);
}
}
}
struct SegmentTree {
long long sum[MAX_NODES * 4], lazy[MAX_NODES * 4];
void build(int node, int start, int end) {
lazy[node] = 0;
if (start == end) {
sum[node] = mapped_values[start] % modulo;
return;
}
int mid = (start + end) / 2;
build(node * 2, start, mid);
build(node * 2 + 1, mid + 1, end);
sum[node] = (sum[node * 2] + sum[node * 2 + 1]) % modulo;
}
void apply_lazy(int node, int start, int end) {
if (lazy[node] != 0) {
sum[node] = (sum[node] + (end - start + 1) * lazy[node]) % modulo;
if (start != end) {
lazy[node * 2] = (lazy[node * 2] + lazy[node]) % modulo;
lazy[node * 2 + 1] = (lazy[node * 2 + 1] + lazy[node]) % modulo;
}
lazy[node] = 0;
}
}
void update_range(int node, int start, int end, int l, int r, long long val) {
apply_lazy(node, start, end);
if (start > end || start > r || end < l) return;
if (start >= l && end <= r) {
sum[node] = (sum[node] + (end - start + 1) * val) % modulo;
if (start != end) {
lazy[node * 2] = (lazy[node * 2] + val) % modulo;
lazy[node * 2 + 1] = (lazy[node * 2 + 1] + val) % modulo;
}
return;
}
int mid = (start + end) / 2;
update_range(node * 2, start, mid, l, r, val);
update_range(node * 2 + 1, mid + 1, end, l, r, val);
sum[node] = (sum[node * 2] + sum[node * 2 + 1]) % modulo;
}
long long query_range(int node, int start, int end, int l, int r) {
if (start > end || start > r || end < l) return 0;
apply_lazy(node, start, end);
if (start >= l && end <= r) return sum[node];
int mid = (start + end) / 2;
long long p1 = query_range(node * 2, start, mid, l, r);
long long p2 = query_range(node * 2 + 1, mid + 1, end, l, r);
return (p1 + p2) % modulo;
}
} seg_tree;
void update_path(int u, int v, long long val) {
while (chain_head[u] != chain_head[v]) {
if (depth[chain_head[u]] < depth[chain_head[v]]) swap(u, v);
seg_tree.update_range(1, 1, total_nodes, pos_in_array[chain_head[u]], pos_in_array[u], val);
u = parent_node[chain_head[u]];
}
if (depth[u] > depth[v]) swap(u, v);
seg_tree.update_range(1, 1, total_nodes, pos_in_array[u], pos_in_array[v], val);
}
long long query_path(int u, int v) {
long long result = 0;
while (chain_head[u] != chain_head[v]) {
if (depth[chain_head[u]] < depth[chain_head[v]]) swap(u, v);
result = (result + seg_tree.query_range(1, 1, total_nodes, pos_in_array[chain_head[u]], pos_in_array[u])) % modulo;
u = parent_node[chain_head[u]];
}
if (depth[u] > depth[v]) swap(u, v);
result = (result + seg_tree.query_range(1, 1, total_nodes, pos_in_array[u], pos_in_array[v])) % modulo;
return result;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> total_nodes >> total_queries >> root_node >> modulo;
for (int i = 1; i <= total_nodes; i++) {
cin >> initial_values[i];
initial_values[i] %= modulo;
}
for (int i = 0; i < total_nodes - 1; i++) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
compute_metrics(root_node, 0, 0);
decompose(root_node, root_node);
seg_tree.build(1, 1, total_nodes);
for (int i = 0; i < total_queries; i++) {
int type;
cin >> type;
if (type == 1) {
int u, v;
long long val;
cin >> u >> v >> val;
update_path(u, v, val % modulo);
} else if (type == 2) {
int u, v;
cin >> u >> v;
cout << query_path(u, v) << "\n";
} else if (type == 3) {
int u;
long long val;
cin >> u >> val;
seg_tree.update_range(1, 1, total_nodes, pos_in_array[u], pos_in_array[u] + subtree_size[u] - 1, val % modulo);
} else if (type == 4) {
int u;
cin >> u;
cout << seg_tree.query_range(1, 1, total_nodes, pos_in_array[u], pos_in_array[u] + subtree_size[u] - 1) << "\n";
}
}
return 0;
}