Heavy-Light Decomposition

Tema: Árboles · temarios: Syllabus OCI · Syllabus IOI

📍 Para profundizar: esta ficha amplía las clases de la Ruta de Aprendizaje. Puedes estudiarla cuando un problema requiera esta herramienta.

Qué hace

Descompone el árbol en cadenas ‘pesadas’ para responder consultas/updates sobre CAMINOS con un segment tree, en O(log² n).

Complejidad: Construcción O(n); consulta de camino O(log² n).

Cuándo usarlo

Consultas (suma/máx) o actualizaciones a lo largo del camino entre dos nodos, muchas veces. Para las subtareas altas de problemas en árboles.

Implementación recomendada (C++)

struct HLD {                                // suma sobre vértices del camino; incluye segtree
    int n, timer = 0;
    vector<vector<int>> g;
    vector<int> par, dep, sz, head, pos;
    vector<long long> seg;
    HLD(int n) : n(n), g(n), par(n,-1), dep(n,0), sz(n,1), head(n,0), pos(n,0), seg(2*n,0) {}
    void add(int u, int v) { g[u].push_back(v); g[v].push_back(u); }
    void dfs_sz(int u, int p) {
        par[u] = p; sz[u] = 1; int big = -1;
        for (int v : g[u]) if (v != p) { dep[v] = dep[u]+1; dfs_sz(v, u); sz[u] += sz[v];
            if (big == -1 || sz[v] > sz[big]) big = v; }
        if (big != -1) { auto it = find(g[u].begin(), g[u].end(), big); swap(*g[u].begin(), *it); }
    }
    void dfs_hld(int u, int p, int h) {
        head[u] = h; pos[u] = timer++;
        bool heavy = true;
        for (int v : g[u]) if (v != p) { dfs_hld(v, u, heavy ? h : v); heavy = false; }
    }
    void build(int root = 0) { dfs_sz(root, -1); dfs_hld(root, -1, root); }
    void update(int u, long long val) {     // asigna val al vértice u
        int i = pos[u] + n; seg[i] = val;
        for (i >>= 1; i >= 1; i >>= 1) seg[i] = seg[2*i] + seg[2*i+1];
    }
    long long qseg(int l, int r) {          // [l, r)
        long long s = 0; for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
            if (l & 1) s += seg[l++]; if (r & 1) s += seg[--r]; } return s;
    }
    long long query_path(int u, int v) {
        long long res = 0;
        while (head[u] != head[v]) {
            if (dep[head[u]] < dep[head[v]]) swap(u, v);
            res += qseg(pos[head[u]], pos[u] + 1);
            u = par[head[u]];
        }
        if (dep[u] > dep[v]) swap(u, v);
        res += qseg(pos[u], pos[v] + 1);
        return res;
    }
};

⚠️ Notas

Por qué O(log n) cadenas: cada vez que un camino usa una arista ligera, el subárbol al menos se duplica, y eso solo puede pasar log n veces. El truco de implementación es colocar el hijo pesado primero y darle la misma head que el padre; de paso, el subárbol de u queda en el rango contiguo [pos[u], pos[u]+sz[u]). Aquí se combina con un segment tree de actualización puntual: para actualizar RANGOS del camino, cámbialo por Segment tree con lazy propagation. Para consultas sobre ARISTAS, asocia cada arista a su hijo y excluye el LCA. ⚠️ La recursión aquí es de profundidad O(n) (un árbol en forma de camino la lleva al máximo). En la IOI eso no es problema: el run_cpp.sh oficial sube la pila al mismo valor que la memoria (2 GB en 2023). En tu propia máquina sí lo es: el límite por defecto son 8 MB y revienta cerca de n = 120.000. Si se cae localmente pero pasa en el juez, es esto — corre ulimit -s unlimited (o ulimit -s 65520 en macOS) antes de probar.

🔗 Relacionados