Centroid 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

Construye el ‘árbol de centroides’: recursivamente elige el centroide, lo quita y recurre. Da una jerarquía de profundidad O(log n).

Complejidad: Construcción O(n log n).

Cuándo usarlo

Contar/agregar caminos en árboles (todos los caminos pasan por el centroide de algún nivel). Problemas de distancias entre pares.

Implementación recomendada (C++)

struct CentroidDecomp {
    int n; vector<vector<int>> g; vector<int> sz; vector<char> removed; vector<int> cpar;
    CentroidDecomp(int n) : n(n), g(n), sz(n,0), removed(n,0), cpar(n,-1) {}
    void add(int u, int v) { g[u].push_back(v); g[v].push_back(u); }
    int calc_sz(int u, int p) {
        sz[u] = 1;
        for (int v : g[u]) if (v != p && !removed[v]) sz[u] += calc_sz(v, u);
        return sz[u];
    }
    int centroid(int u, int p, int tot) {
        for (int v : g[u]) if (v != p && !removed[v] && sz[v] > tot/2) return centroid(v, u, tot);
        return u;
    }
    void build(int u, int cp) {
        int tot = calc_sz(u, -1), c = centroid(u, -1, tot);
        cpar[c] = cp; removed[c] = 1;
        for (int v : g[c]) if (!removed[v]) build(v, c);
    }
    void run() { build(0, -1); }            // cpar[c] = padre de c en el árbol de centroides
};

⚠️ Notas

Por qué la profundidad es O(log n): el centroide deja todos los subárboles con a lo más n/2 nodos, así que el tamaño se reduce a la mitad en cada nivel. La clave del uso: cualquier camino u→v pasa por el centroide del nivel más alto que los separa, así que procesas cada camino una sola vez. El esqueleto típico: parado en un centroide, recolecta las distancias de cada subárbol al centroide, cuenta los pares que cumplen la condición, y resta los pares que quedaron dentro de un mismo subárbol (esos no pasan por el centroide). ⚠️ 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