OIA-Wiki

Árboles

Noción de programación dinámica

Algo que es muy usual es querer saber información sobre muchos subárboles. Por ejemplo, si queremos saber cuántos nodos tienen subárbol de tamaño mayor a $x$. (Notar que el árbol debe tener una raíz definida para que tenga sentido hablar de subárboles.)

Para resolver esto vamos utilizar programación dinámica.

De arriba para abajo

Vamos a empezar en la raíz y usar la misma fórmula que arriba, con la excepción de que ahora no tenemos todavía la información de abajo. Entonces usaremos recursión. Para saber el tamaño del subárbol de la raíz (que en realidad es la cantidad de nodos pero igualmente empezamos por acá para recorrer todo el árbol), llamamos a la función que calcula el tamaño de un subárbol para cada uno de sus hijos. Y una vez que ya tenemos esos datos, los sumamos y luego sumamos $1$.

El código quedaría:

map<int,int> tamanioDeNodo;
 
int tamanio(int nodo, int padre){
    int miTamanio=1;
    for(int i=0; i<grafo[nodo].size(); i++){ // Los casos base de esta recursión serían las hojas, ya que no tienen nodos adyacentes distintos del padre y el if no pasa y entonces no se llama a la función recursiva
        if(grafo[nodo][i]!=padre){
            miTamanio+=tamanio(grafo[nodo][i], nodo);
        }
    }
    tamanioDeNodo[nodo]=miTamanio;
    return miTamanio;
}
 
tamanio(raiz, -1);

Dado un árbol de $N$ nodos, el nodo $i$ tiene $M_i$ monedas. Tenés que seleccionar un conjunto de nodos, de manera que no haya dos que sean adyacentes de ese conjunto, tal que la suma de las monedas de los nodos seleccionados sea la mayor posible.

Pensemos qué pasa si vamos recorriendo el árbol desde la raíz hacia abajo (seteando primero alguna raíz), y obteniendo información sobre subárboles. Lo que podemos pensar es que si estamos mirando un nodo, podemos seleccionarlo o no. Entonces vamos a mirar las dos opciones. Obviamente no vamos a pensar qué pasa en cada subconjunto posible del conjunto de nodos, eso tomaría $O(2^N)$ operaciones. Para eso vamos a usar la programación dinámica, que es más o menos “mirar todas las posibilidades” pero de una “manera inteligente”.

Entonces, si estamos en el nodo $u$, y sólo nos importa el subárbol del nodo $u$ (para eso vamos a ir de arriba hacia abajo), podemos o seleccionarlo o no. Si lo seleccionamos, luego no podremos seleccionar a ninguno de los hijos. Entonces las monedas que podemos obtener son las monedas del nodo $u$, $M_u$, más la mayor cantidad de monedas de los hijos de los hijos de $u$, ya que, como a sus hijos no los vamos a poder seleccionar, para los subárboles de los hijos de los hijos no tendremos ninguna restricción que nos impida seleccionar lo que queramos.

Y si no seleccionamos el nodo $u$, vamos a poder hacer lo que queramos con los subárboles de los hijos de $u$, ya que no tendrán ninguna restricción. Además, es importante notar que como estos subárboles son disjuntos, seleccionemos lo que seleccionemos del subárbol de uno de los hijos no afecta lo que podamos seleccionar del subárbol de otro de los hijos.

Entonces ya tenemos la manera de obtener lo mejor para un subárbol: O es la cantidad de monedas de la raíz del subárboles más la suma de las mejores cantidades para los subárboles de los hijos de los hijos de esta raíz; o es la suma de las mejor cantidades de los subárboles de sus hijos. Vamos a hacerlo, como se ve, recursivamente. Hasta que lleguemos a una hoja, donde la mejor cantidad para el subárbol de la raíz es simplemente la cantidad de monedas que hay en esa hoja (caso base).

Para esto, vamos a tener una función recursiva “recorroSubarbolYGuardo”, que dado un nodo y su padre, obtenga el mejor valor del subárbol (la solución parcial en programación dinámica), usando y sin usar el nodo. Cómo? Llamando a la función para los subárboles de los hijos y usando esa información como vimos antes.

// Tenemos el grafo en "vector< vector<int> > grafo" y un vector<int> monedas con Mi en la posición i
const int MAXN=1e5;
 
vector<int> mejorSinUsar(MAXN), mejorUsando(MAXN);
 
void recorroSubarbolYGuardo(int nodo, int padre){
    int cantidadUsandoNodo = monedas[nodo];
    int cantidadSinUsar=0;
    for(int i=0; i<grafo[nodo].size(); i++){
        int hijo=grafo[nodo][i];
        if(hijo!=padre){
            recorroSubarbolYGuardo(hijo, nodo);
            cantidadUsandoNodo+=mejorSinUsar[hijo];
            cantidadSinUsar+=max(mejorUsando[hijo], mejorSinUsar[hijo]); // Como no hay restricción, quizás nos conviene seleccionar al hijo pero quizás no, entonces nos quedamos con la mejor de ambas posibilidades
        }
    }
    mejorSinUsar[nodo]=cantidadSinUsar;
    mejorUsando[nodo]=cantidadUsandoNodo;
}
 
recorroSubarbolYGuardo(0, -1);
 
cout<<max(mejorSinUsar[0], mejorUsando[0])<<endl;

Mismo que el de las monedas

Maximizar peso

Parecido al de las monedas (ojo con los pesos negativos!)

http://codeforces.com/blog/entry/20935