Conceptos Básicos de DP en Árboles

La programación dinámica (DP) en estructuras de árbol es una herramienta esencial para resolver problemas de optimización. Al trabajar con árboles, su naturaleza recursiva permite descomponer el problema en subproblemas más pequeños, facilitando el uso de memorización para calcular soluciones óptimas de manera eficiente.

Árbol de Manzanas Optimizado

Descripción del problema: Se tiene un árbol con n nodos etiquetados del 1 al n, donde el nodo raíz es el 1. Las ramas se definen por pares de nodos y un valor de manzanas asociado. El objetivo es seleccionar exactamente q ramas para maximizar el número total de manzanas conservadas.

Análisis de la solución: Definimos dp[nodo][ramas] como el máximo de manzanas que se pueden obtener en el subárbol con raíz en nodo al seleccionar ramas aristas. La solución final es dp[raíz][q]. Para cada nodo, consideramos sus hijos y distribuimos las aristas entre ellos de forma óptima.

Código de ejemplo (modificado para mayor claridad):

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int MAX_NODOS = 205;
vector<pair int="">> grafo[MAX_NODOS];  // Almacena (hijo, peso)
int memo[MAX_NODOS][MAX_NODOS];
int total_aristas[MAX_NODOS];
int n, limite;

void calcularDP(int nodo, int padre) {
    total_aristas[nodo] = 0;
    for (int i = 0; i < grafo[nodo].size(); i++) {
        int hijo = grafo[nodo][i].first;
        int valor = grafo[nodo][i].second;
        if (hijo == padre) continue;
        calcularDP(hijo, nodo);
        total_aristas[nodo] += total_aristas[hijo] + 1;
        for (int j = min(limite, total_aristas[nodo]); j >= 0; j--) {
            for (int k = 0; k <= min(total_aristas[hijo], j - 1); k++) {
                memo[nodo][j] = max(memo[nodo][j], memo[nodo][j - k - 1] + memo[hijo][k] + valor);
            }
        }
    }
}

int main() {
    cin >> n >> limite;
    for (int i = 0; i < n - 1; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        grafo[u].emplace_back(v, w);
        grafo[v].emplace_back(u, w);
    }
    calcularDP(1, 0);
    cout << memo[1][limite] << endl;
    return 0;
}</pair>

En este código, se utiliza un enfoque de recorrido post-orden para calcular la DP. El bucle interno sobre j se realiza en orden descendente para evitar sobrescritura incorrecta de valores durante la transición de estados.

Máxima Suma de Pesos tras Eliminar Aristas

Descripción del problema: Dado un árbol no dirigido con n nodos y aristas ponderadas, se deben eliminar algunas aristas de modo que cada nodo tenga un grado máximo de k. El objetivo es maximizar la suma de los pesos de las aristas restantes.

Análisis de la solución: Un enfoque greedy simple no es suficiente, ya que decisiones locales pueden no ser óptimas globalmente. En cambio, se utiliza una combinación de DP en árbol y estrategias de selección basadas en incrementos. Para cada nodo, calculamos dos valores: el máximo cuando no se incluye la arista al padre y el máximo cuando sí se incluye, considerando las restricciones de grado.

Implementación en C++ (versión reestructurada):

#include <vector>
#include <algorithm>
#include <functional>
using namespace std;

long long calcularMaximo(vector<vector<pair<int, int>>>& adyacencia, int k) {
    int num_nodos = adyacencia.size();
    auto dfs = [&](auto& dfs, int nodo, int padre) -> pair<long long, long long> {
        long long sin_elegir = 0;
        vector<long long> incrementos;
        for (auto& [hijo, peso] : adyacencia[nodo]) {
            if (hijo == padre) continue;
            auto [nc, c] = dfs(dfs, hijo, nodo);
            sin_elegir += nc;
            long long delta = c + peso - nc;
            if (delta > 0) incrementos.push_back(delta);
        }
        sort(incrementos.begin(), incrementos.end(), greater<long long>());
        for (int i = 0; i < min((int)incrementos.size(), k - 1); i++) {
            sin_elegir += incrementos[i];
        }
        long long con_elegir = sin_elegir;
        if (incrementos.size() >= k) sin_elegir += incrementos[k - 1];
        return {sin_elegir, con_elegir};
    };
    return dfs(dfs, 0, -1).first;
}

Este código utiliza un recorrido DFS para calcular los estados óptimos. La clave está en seleccionar los incrementos más altos para maximizar la suma bajo las retsricciones de grado.

Representación con Hijo Izquierdo y Hermano Derecho

Descripción del problema: Para un árbol multi-way con N nodos, se debe convertir a un árbol binario usando la representación "hijo izquierod, hermano derecho". Los nodos hijos son desordenados, por lo que la conversión no es única. El objetivo es determinar la altura máxima posible del árbol binario resultante, donde la raíz tiene profundidad 0.

Análisis de la solución: La altura del árbol binario depende de cómo se elige el hijo izquierdo y se ordenan los hermanos. Para maximizar la altura, se puede colocar el subárbol con mayor altura como el hijo izquierdo y encadenar los hermanos restantes como subárbol derecho. Esto se reduce a un problema recursivo de calcular la altura máxima para cada subárbol.

Código simplificado (con nombres de variables alternativos):

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int obtenerAlturaMaxima(int raiz, vector<vector<int>>& hijos) {
    int max_altura = 0;
    for (int hijo : hijos[raiz]) {
        max_altura = max(max_altura, obtenerAlturaMaxima(hijo, hijos));
    }
    return max_altura + hijos[raiz].size();
}

int main() {
    int n;
    cin >> n;
    vector<vector<int>> hijos(n + 1);
    for (int i = 2; i <= n; i++) {
        int padre;
        cin >> padre;
        hijos[padre].push_back(i);
    }
    cout << obtenerAlturaMaxima(1, hijos) << endl;
    return 0;
}

Este código implementa un enfoque recursivo para calcular la altura, donde la función suma el número de hijos al máximo de las alturas de los subárboles hijos.