Centroide en Árboles

El centroide minimiza la suma de distancias a todos los nodos. Definimos:

• dist[i]: Suma de distancias desde nodos en el subárbol con raíz en i
• tam[i]: Tamaño del subárbol con raíz en i

Para hojas: dist[i] = 0. Relación recursiva:

void calcular(int nodo, int padre) {
    for (int hijo : grafo[nodo]) {
        if (hijo == padre) continue;
        calcular(hijo, nodo);
    }
    dist[nodo] = 0;
    tam[nodo] = 1;
    for (int hijo : grafo[nodo]) {
        if (hijo == padre) continue;
        tam[nodo] += tam[hijo];
        dist[nodo] += dist[hijo] + tam[hijo];
    }
}

Reenraizamiento

Al mover la raíz de 1 a p:

void reenraizar(int nodo, int padre, int suma_externa) {
    resultado = min(resultado, dist[nodo] + suma_externa);
    for (int hijo : grafo[nodo]) {
        if (hijo == padre) continue;
        int nueva_suma = suma_externa + dist[nodo] - (dist[hijo] + tam[hijo]) + (n - tam[hijo]);
        reenraizar(hijo, nodo, nueva_suma);
    }
}

Programación Dinámica con Estado Comprimido

Resolevr el problema del vendedor viajero (TSP):

double dp[1<<max al="" distancia="" dp="" en="" for="" i="" if="" inf="" inicializaci="" int="" m="" main="" mascara="" n="" nodos="" terminando="" visitar="">> i & 1) 
                for (int j = 0; j < n; j++) 
                    if (!(mascara >> j & 1)) 
                        dp[mascara|(1<<j distancia="" dp="" j="" min=""></j></max>

Programación Dinámica de Dígitos

Caclular suma de dígitos en rango [L, R]:

int digito_dp(int limite) {
    vector<int> digitos;
    while (limite) {
        digitos.push_back(limite % 10);
        limite /= 10;
    }
    reverse(digitos.begin(), digitos.end());
    
    pair<int, int> dp[digitos.size()+1][2]; // {suma, conteo}
    dp[0][1] = {0, 1};
    
    for (int pos = 0; pos < digitos.size(); pos++) 
        for (int tight : {0, 1}) 
            if (dp[pos][tight].second) 
                for (int d = 0; d <= (tight ? digitos[pos] : 9); d++) {
                    int nuevo_tight = tight && (d == digitos[pos]);
                    dp[pos+1][nuevo_tight].first += dp[pos][tight].first + d * dp[pos][tight].second;
                    dp[pos+1][nuevo_tight].second += dp[pos][tight].second;
                }
    
    return dp[digitos.size()][0].first + dp[digitos.size()][1].first;
}

Ejemplo: Colocación de Reyes

Solución con DP de estado comprimido:

long long dp[2][1<<12][100];
// dp[i][mascara][reyes] = conteo para fila i con máscara y k reyes

int main() {
    dp[0][0][0] = 1;
    for (int fila = 0; fila < n; fila++) 
        for (int mascara = 0; mascara < (1<<n :="" cnt="__builtin_popcount(nueva);" continue="" dp="" estados_validos="" for="" horizontal="" if="" int="" k="" mascara="" nueva="" reyes="0;" vertical=""></n>