OIA-Wiki

Árboles

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.

Lo podemos hacer de dos maneras escencialmente:

De abajo para arriba: Empezar en las hojas, marcando como que sus subárboles tienen tamaño $0$, y a partir de ahí ir a sus padres, y sabemos que sus subárboles tienen $cantidadDeHijosDelNodo + 1$, en este caso. Y en general, si vamos subiendo, sabemos que el tamaño de un subárbol es la suma de los tamaños de los subárboles de sus hijos, más $1$.

Si tenemos un nodo $raiz$, un $vector< vector<int> > grafo$ y un $vector<int> tamanio$ que en la posición $i$ vaya a quedar el tamanio del subárbol del nodo $i$, el código quedaría:

vector<int> tamanio(V, -1);
 
queue<int> nodosQueYaPasePorSusHijos;
forn(i, V){
    if(esHoja(i)){
        tamanio[i]=1;
        nodosQueYaPasePorSusHijos.push(i);
    }
}
 
while(!nodosQueYaPasePorSusHijos.empty()){
    int nodo = nodosQueYaPasePorSusHijos.front();
    nodosQueYaPasePorSusHijos.pop();
    int miTamanio=1; // Por el nodo "raiz del subarbol"
    int padre=-1;
    forn(i, grafo[nodo].size()){
        if(tamanio[grafo[nodo][i]]!=-1){ // Para no mirar el padre que todavia no sabemos el tamanio
            miTamanio+=tamanio[grafo[nodo][i]];
        }else{
            padre=grafo[nodo][i]
        }
    }
    tamanio[nodo]=miTamanio;
    if(padre!=-1){
        nodosQueYaPasePorSusHijos.push(padre);
    }
}

Algo que hay que tener en cuenta es cómo implementar la función “esHoja” utilizada acá. Una manera de encontrar las hojas, es empezar en la raíz, ir recorriendo un bfs/dfs, y cuando desde un nodo no hay vecinos a los que ir, es porque su vecino es su padre y no tiene hijos, entonces es hoja.

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);

problemas