La descomposición de cadenas pesadas consiste en particionar un árbol con raíz en múltiples cadenas pesadas para administrar su información mediante estructuras de datos eficientes.
Problema típico
Considerando un árbol con raíz, se requieren las siguientes operaciones:
- Sumar un valer z a todos los nodos en el camino más corto entre los nodos x e y.
- Calcular la suma de los valores de todos los nodos en el camino más corto entre los nodos x e y.
Conceptos clave
- Hijo pesado: El hijo con mayor tamaño de subárbol entre todos los hijos de un nodo padre.
- Hijo ligero: Cualquier hijo que no sea el hijo pesado.
- Arista pesada: Conecta un nodo padre con su hijo pesado.
- Arista ligera: Conecta un nodo padre con un hijo ligero.
- Cadena pesada: Ruta formada por múltiples aristas pesadas consecutivas.
- Cadena ligera: Ruta formada por múltiples aristas ligeras consecutivas.
Variables de preprocesamiento
sub_size[v]- Tamaño del subárbol del nodo v.depth[v]- Profundidad del nodo v.parent[v]- Padre del nodo v.heavy_child[v]- Hijo pesado del nodo v (nulos para hojas).chain_top[v]- Nodo superior de la cadena pesada que conitene a v.dfs_order[v]- Nuevo índice (orden DFS) asignado al nodo v.
Implementación del preprocesamiento
Se realizan dos recorridos DFS.
Primer DFS calcula los tamaños de subárbol, profundidades, padres e hijos pesados:
void first_dfs(int node, int par) {
sub_size[node] = 1;
depth[node] = depth[par] + 1;
parent[node] = par;
int max_sub_size = 0;
for (int child : adjacency[node]) {
if (child == par) continue;
first_dfs(child, node);
sub_size[node] += sub_size[child];
if (sub_size[child] > max_sub_size) {
max_sub_size = sub_size[child];
heavy_child[node] = child;
}
}
}
Segundo DFS asigna las cadenas superiores y el orden DFS, garantizanod que los nodos en una misma cadena pesada tengan índices consecutivos:
int current_idx = 0;
void second_dfs(int node, int top_chain) {
chain_top[node] = top_chain;
dfs_order[node] = ++current_idx;
segment_tree.update(current_idx, current_idx, node_value[node]);
if (heavy_child[node]) {
second_dfs(heavy_child[node], top_chain);
}
for (int child : adjacency[node]) {
if (child == parent[node] || child == heavy_child[node]) continue;
second_dfs(child, child);
}
}
Operaciones
Para consultas y modificaciones en la ruta entre dos nodos, se "saltan" hacia arriba en las cadenas pesadas utilizando la información de chain_top, similar a la búsqueda del ancestro común más bajo (LCA). La estructura de segmentos gestiona eficientemente las operaciones de rango dentro de cada cadena.
Ejemplo: Operaciones en caminos y subárboles
Problema que requiere soporte para:
- Sumar z a todos los nodos en la ruta entre x e y.
- Consultar la suma en la ruta entre x e y.
- Sumar z a todos los nodos en el subárbol de x.
- Consultar la suma en el subárbol de x.
Las consultas de subárbol se benefician del orden DFS consecutivo de todo el subárbol.
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
int node_val[MAXN];
// Segment Tree con lazy propagation
long long seg_tree[4 * MAXN];
long long lazy_mark[4 * MAXN];
int tree_size;
void propagate(int idx, int left, int right, int mid) {
if (lazy_mark[idx] != 0) {
lazy_mark[idx * 2] += lazy_mark[idx];
lazy_mark[idx * 2 + 1] += lazy_mark[idx];
seg_tree[idx * 2] += lazy_mark[idx] * (mid - left + 1);
seg_tree[idx * 2 + 1] += lazy_mark[idx] * (right - mid);
lazy_mark[idx] = 0;
}
}
void range_add(int idx, int left, int right, int ql, int qr, long long val) {
if (ql <= left && right <= qr) {
seg_tree[idx] += val * (right - left + 1);
lazy_mark[idx] += val;
return;
}
int mid = (left + right) / 2;
propagate(idx, left, right, mid);
if (ql <= mid) range_add(idx * 2, left, mid, ql, qr, val);
if (qr > mid) range_add(idx * 2 + 1, mid + 1, right, ql, qr, val);
seg_tree[idx] = seg_tree[idx * 2] + seg_tree[idx * 2 + 1];
}
long long range_query(int idx, int left, int right, int ql, int qr) {
if (ql <= left && right <= qr) {
return seg_tree[idx];
}
int mid = (left + right) / 2;
propagate(idx, left, right, mid);
long long res = 0;
if (ql <= mid) res += range_query(idx * 2, left, mid, ql, qr);
if (qr > mid) res += range_query(idx * 2 + 1, mid + 1, right, ql, qr);
return res;
}
// Datos del árbol
vector<int> tree_edges[MAXN];
int sub_size[MAXN], depth[MAXN], parent[MAXN];
int heavy_child[MAXN], chain_top[MAXN], dfs_order[MAXN];
int n, m, root, mod_val;
// Primer DFS
void preprocess_sizes(int node, int par) {
sub_size[node] = 1;
depth[node] = depth[par] + 1;
parent[node] = par;
int max_size = 0;
for (int child : tree_edges[node]) {
if (child == par) continue;
preprocess_sizes(child, node);
sub_size[node] += sub_size[child];
if (sub_size[child] > max_size) {
max_size = sub_size[child];
heavy_child[node] = child;
}
}
}
// Segundo DFS
int order_counter = 0;
void decompose_chains(int node, int top_chain) {
chain_top[node] = top_chain;
dfs_order[node] = ++order_counter;
range_add(1, 1, n, order_counter, order_counter, node_val[node]);
if (heavy_child[node]) {
decompose_chains(heavy_child[node], top_chain);
}
for (int child : tree_edges[node]) {
if (child == parent[node] || child == heavy_child[node]) continue;
decompose_chains(child, child);
}
}
// Operaciones en caminos
void path_update(int u, int v, long long z) {
while (chain_top[u] != chain_top[v]) {
if (depth[chain_top[u]] < depth[chain_top[v]]) swap(u, v);
range_add(1, 1, n, dfs_order[chain_top[u]], dfs_order[u], z);
u = parent[chain_top[u]];
}
if (depth[u] < depth[v]) swap(u, v);
range_add(1, 1, n, dfs_order[v], dfs_order[u], z);
}
long long path_query(int u, int v) {
long long sum = 0;
while (chain_top[u] != chain_top[v]) {
if (depth[chain_top[u]] < depth[chain_top[v]]) swap(u, v);
sum += range_query(1, 1, n, dfs_order[chain_top[u]], dfs_order[u]);
u = parent[chain_top[u]];
}
if (depth[u] < depth[v]) swap(u, v);
sum += range_query(1, 1, n, dfs_order[v], dfs_order[u]);
return sum % mod_val;
}
// Operaciones en subárboles
void subtree_update(int root_node, long long z) {
range_add(1, 1, n, dfs_order[root_node], dfs_order[root_node] + sub_size[root_node] - 1, z);
}
long long subtree_query(int root_node) {
return range_query(1, 1, n, dfs_order[root_node], dfs_order[root_node] + sub_size[root_node] - 1) % mod_val;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m >> root >> mod_val;
for (int i = 1; i <= n; ++i) cin >> node_val[i];
for (int i = 1; i < n; ++i) {
int u, v;
cin >> u >> v;
tree_edges[u].push_back(v);
tree_edges[v].push_back(u);
}
preprocess_sizes(root, 0);
decompose_chains(root, root);
for (int i = 0; i < m; ++i) {
int op;
cin >> op;
if (op == 1) {
int x, y, z;
cin >> x >> y >> z;
path_update(x, y, z);
} else if (op == 2) {
int x, y;
cin >> x >> y;
cout << path_query(x, y) << "\n";
} else if (op == 3) {
int x, z;
cin >> x >> z;
subtree_update(x, z);
} else {
int x;
cin >> x;
cout << subtree_query(x) << "\n";
}
}
return 0;
}
Ejemplo: Gestión de instancias de software
Se modela un árbol de dependencias. La operación instalar cambia el estado de todos los nodos desde la raíz hasta el paquete objetivo a "instalado". La operación desinstalar resetea el estado de todo el subárbol del objetivo a "no instalado". Se mantiene un contador de cambios.
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
int n;
vector<int> dependency_tree[MAXN];
int seg_data[4 * MAXN];
struct LazyTag {
int value;
int timestamp;
} seg_lazy[4 * MAXN];
int global_clock = 0;
// Segment Tree con marcas de tiempo para gestionar prioridad de actualizaciones
void propagate(int idx, int left, int right, int mid) {
if (seg_lazy[idx].timestamp == 0) return;
if (seg_lazy[idx * 2].timestamp < seg_lazy[idx].timestamp) {
seg_lazy[idx * 2] = seg_lazy[idx];
}
if (seg_lazy[idx * 2 + 1].timestamp < seg_lazy[idx].timestamp) {
seg_lazy[idx * 2 + 1] = seg_lazy[idx];
}
seg_data[idx * 2] = seg_lazy[idx * 2].value * (mid - left + 1);
seg_data[idx * 2 + 1] = seg_lazy[idx * 2 + 1].value * (right - mid);
seg_lazy[idx] = {0, 0};
}
void assign_range(int idx, int left, int right, int ql, int qr, int val) {
if (ql <= left && right <= qr) {
seg_data[idx] = val * (right - left + 1);
seg_lazy[idx] = {val, ++global_clock};
return;
}
int mid = (left + right) / 2;
propagate(idx, left, right, mid);
if (ql <= mid) assign_range(idx * 2, left, mid, ql, qr, val);
if (qr > mid) assign_range(idx * 2 + 1, mid + 1, right, ql, qr, val);
seg_data[idx] = seg_data[idx * 2] + seg_data[idx * 2 + 1];
}
int query_range(int idx, int left, int right, int ql, int qr) {
if (ql <= left && right <= qr) {
return seg_data[idx];
}
int mid = (left + right) / 2;
propagate(idx, left, right, mid);
int res = 0;
if (ql <= mid) res += query_range(idx * 2, left, mid, ql, qr);
if (qr > mid) res += query_range(idx * 2 + 1, mid + 1, right, ql, qr);
return res;
}
// Descomposición del árbol
int sub_size[MAXN], depth[MAXN], parent[MAXN];
int heavy_child[MAXN], chain_top[MAXN], dfs_order[MAXN];
int order_cnt = 0;
void calc_heavy_paths(int node, int par) {
sub_size[node] = 1;
depth[node] = depth[par] + 1;
parent[node] = par;
int max_sub = 0;
for (int child : dependency_tree[node]) {
if (child == par) continue;
calc_heavy_paths(child, node);
sub_size[node] += sub_size[child];
if (sub_size[child] > max_sub) {
max_sub = sub_size[child];
heavy_child[node] = child;
}
}
}
void build_heavy_paths(int node, int top) {
chain_top[node] = top;
dfs_order[node] = ++order_cnt;
if (heavy_child[node]) {
build_heavy_paths(heavy_child[node], top);
}
for (int child : dependency_tree[node]) {
if (child == parent[node] || child == heavy_child[node]) continue;
build_heavy_paths(child, child);
}
}
int query_path(int u, int v) {
int res = 0;
while (chain_top[u] != chain_top[v]) {
if (depth[chain_top[u]] < depth[chain_top[v]]) swap(u, v);
res += query_range(1, 1, n, dfs_order[chain_top[u]], dfs_order[u]);
u = parent[chain_top[u]];
}
if (depth[u] < depth[v]) swap(u, v);
res += query_range(1, 1, n, dfs_order[v], dfs_order[u]);
return res;
}
void modify_path(int u, int v, int val) {
while (chain_top[u] != chain_top[v]) {
if (depth[chain_top[u]] < depth[chain_top[v]]) swap(u, v);
assign_range(1, 1, n, dfs_order[chain_top[u]], dfs_order[u], val);
u = parent[chain_top[u]];
}
if (depth[u] < depth[v]) swap(u, v);
assign_range(1, 1, n, dfs_order[v], dfs_order[u], val);
}
int query_subtree(int root_node) {
return query_range(1, 1, n, dfs_order[root_node], dfs_order[root_node] + sub_size[root_node] - 1);
}
void modify_subtree(int root_node, int val) {
assign_range(1, 1, n, dfs_order[root_node], dfs_order[root_node] + sub_size[root_node] - 1, val);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (int i = 1; i < n; ++i) {
int par;
cin >> par;
dependency_tree[i].push_back(par);
dependency_tree[par].push_back(i);
}
calc_heavy_paths(0, n); // Raíz virtual
build_heavy_paths(0, 0);
int queries;
cin >> queries;
while (queries--) {
string command;
int package_id;
cin >> command >> package_id;
if (command == "install") {
int currently_installed = query_path(0, package_id);
modify_path(0, package_id, 1);
int new_installed = query_path(0, package_id);
cout << (new_installed - currently_installed) << "\n";
} else {
cout << query_subtree(package_id) << "\n";
modify_subtree(package_id, 0);
}
}
return 0;
}
Ejemplo: Segmentos de color en un camino
Problema que requiere pintar caminos y contar segmentos de color contiguos. La estructura de segmentos almacena el color izquierdo, derecho y el número de segmentos en un intervalo. La combinación de intervalos considera la fusión de segmentos en el límite.
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
int initial_color[MAXN], mapped_color[MAXN];
int n, m;
struct SegmentInfo {
int left_color, right_color;
int segment_count;
SegmentInfo() : left_color(0), right_color(0), segment_count(0) {}
SegmentInfo(int lc, int rc, int cnt) : left_color(lc), right_color(rc), segment_count(cnt) {}
};
SegmentInfo merge_segments(const SegmentInfo &a, const SegmentInfo &b) {
if (a.segment_count == 0) return b;
if (b.segment_count == 0) return a;
SegmentInfo res;
res.left_color = a.left_color;
res.right_color = b.right_color;
res.segment_count = a.segment_count + b.segment_count;
if (a.right_color == b.left_color) {
res.segment_count--;
}
return res;
}
SegmentInfo seg_data[4 * MAXN];
struct PaintTag {
int color;
int timestamp;
} seg_lazy[4 * MAXN];
int global_time = 0;
void propagate(int idx, int left, int right, int mid) {
if (seg_lazy[idx].timestamp == 0) return;
if (seg_lazy[idx * 2].timestamp < seg_lazy[idx].timestamp) {
seg_lazy[idx * 2] = seg_lazy[idx];
}
if (seg_lazy[idx * 2 + 1].timestamp < seg_lazy[idx].timestamp) {
seg_lazy[idx * 2 + 1] = seg_lazy[idx];
}
seg_data[idx * 2] = SegmentInfo(seg_lazy[idx].color, seg_lazy[idx].color, 1);
seg_data[idx * 2 + 1] = SegmentInfo(seg_lazy[idx].color, seg_lazy[idx].color, 1);
seg_lazy[idx] = {0, 0};
}
void paint_range(int idx, int left, int right, int ql, int qr, int color) {
if (ql <= left && right <= qr) {
seg_data[idx] = SegmentInfo(color, color, 1);
seg_lazy[idx] = {color, ++global_time};
return;
}
int mid = (left + right) / 2;
propagate(idx, left, right, mid);
if (ql <= mid) paint_range(idx * 2, left, mid, ql, qr, color);
if (qr > mid) paint_range(idx * 2 + 1, mid + 1, right, ql, qr, color);
seg_data[idx] = merge_segments(seg_data[idx * 2], seg_data[idx * 2 + 1]);
}
SegmentInfo query_range(int idx, int left, int right, int ql, int qr) {
if (ql <= left && right <= qr) {
return seg_data[idx];
}
int mid = (left + right) / 2;
propagate(idx, left, right, mid);
SegmentInfo res;
if (ql <= mid) res = merge_segments(res, query_range(idx * 2, left, mid, ql, qr));
if (qr > mid) res = merge_segments(res, query_range(idx * 2 + 1, mid + 1, right, ql, qr));
return res;
}
// Descomposición del árbol
vector<int> graph[MAXN];
int sub_size[MAXN], depth[MAXN], parent[MAXN];
int heavy_child[MAXN], chain_top[MAXN], dfs_order[MAXN];
int order_idx = 0;
void find_heavy_edges(int node, int par) {
sub_size[node] = 1;
depth[node] = depth[par] + 1;
parent[node] = par;
int max_child_size = 0;
for (int child : graph[node]) {
if (child == par) continue;
find_heavy_edges(child, node);
sub_size[node] += sub_size[child];
if (sub_size[child] > max_child_size) {
max_child_size = sub_size[child];
heavy_child[node] = child;
}
}
}
void assign_chains(int node, int top) {
chain_top[node] = top;
dfs_order[node] = ++order_idx;
mapped_color[order_idx] = initial_color[node];
if (heavy_child[node]) {
assign_chains(heavy_child[node], top);
}
for (int child : graph[node]) {
if (child == parent[node] || child == heavy_child[node]) continue;
assign_chains(child, child);
}
}
SegmentInfo query_path_segments(int u, int v) {
SegmentInfo left_part, right_part;
while (chain_top[u] != chain_top[v]) {
if (depth[chain_top[u]] > depth[chain_top[v]]) {
left_part = merge_segments(query_range(1, 1, n, dfs_order[chain_top[u]], dfs_order[u]), left_part);
u = parent[chain_top[u]];
} else {
right_part = merge_segments(query_range(1, 1, n, dfs_order[chain_top[v]], dfs_order[v]), right_part);
v = parent[chain_top[v]];
}
}
if (depth[u] > depth[v]) {
left_part = merge_segments(query_range(1, 1, n, dfs_order[v], dfs_order[u]), left_part);
} else {
right_part = merge_segments(query_range(1, 1, n, dfs_order[u], dfs_order[v]), right_part);
}
swap(left_part.left_color, left_part.right_color); // Invertir para la combinación final
return merge_segments(left_part, right_part);
}
void paint_path(int u, int v, int color) {
while (chain_top[u] != chain_top[v]) {
if (depth[chain_top[u]] < depth[chain_top[v]]) swap(u, v);
paint_range(1, 1, n, dfs_order[chain_top[u]], dfs_order[u], color);
u = parent[chain_top[u]];
}
if (depth[u] < depth[v]) swap(u, v);
paint_range(1, 1, n, dfs_order[v], dfs_order[u], color);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
for (int i = 1; i <= n; ++i) {
cin >> initial_color[i];
}
for (int i = 1; i < n; ++i) {
int u, v;
cin >> u >> v;
graph[u].push_back(v);
graph[v].push_back(u);
}
find_heavy_edges(1, 0);
assign_chains(1, 1);
for (int i = 1; i <= n; ++i) {
paint_range(1, 1, n, dfs_order[i], dfs_order[i], mapped_color[dfs_order[i]]);
}
for (int i = 0; i < m; ++i) {
char op;
int a, b, c;
cin >> op;
if (op == 'C') {
cin >> a >> b >> c;
paint_path(a, b, c);
} else {
cin >> a >> b;
cout << query_path_segments(a, b).segment_count << "\n";
}
}
return 0;
}