OIA-Wiki

En un árbol, ¿cuál es la longitud del camino más largo entre un par de nodos?

Lo que pide el enunciado se conoce como el diámetro del árbol.

Pensemos primero un poco qué pasa si tenemos un árbol que tiene una raíz. Cómo será el camino más largo del árbol? Bueno, una característica es que los extremos de este camino van a ser hojas. Ya que si alguno no lo fuera, podríamos seguir extendiendo el camino y obtener uno más largo.

El tema entonces está en ver qué dos hojas serán los extremos del camino.

Veamos que el camino entre dos hojas tiene como longitud la suma de las distancia desde las hojas en cuestión hasta el padre común de las hojas.

Ahora, supongamos que el camino más largo se tiene entre las hojas $h_1$ y $h_2$, cuyo padre común es $p$.

Qué pasa si hay una hoja $H$ que tiene mayor altura que $h_1$ y $h_2$? El camino desde esta hoja $H$ hasta $h_1$ tendrá como longitud la suma de las distancias desde $H$ y $h_1$ hasta su padre común. Lo mismo para el camino de $H$ a $h_2$. Si el $H$ no está en el subárbol de $p$, entonces el padre común entre $H$ y cualquiera de $h_1$ y $h_2$ estará más arriba que $p$, y el camino desde $H$ hasta $h_1$ será la distancia entre $h_1$ y $p$, más la distancia de $p$ al padre común de $H$ y $h_1$, más la distancia desde este padre común hasta $H$. Pero este último sumando será mayor a la distancia entre $p$ y $h_2$, por lo que el camino entre $H$ y $h_1$ será mayor al de $h_1$ y $h_2$, absurdo porque este último camino es el más largo.

Ahora, veamos qué pasa si $H$ está en el subárbol de $p$. $H$ no puede ser $p$ porque tendría altura menor a $h_1$ y $h_2$. Ahora, veamos que $h_1$ y $h_2$ están en subárboles de hijos distintos de $p$. Si no, el ancestro común más bajo sería el un hijo de $p$. Luego, si $H$ está en el subárbol de $p$, o bien está en el subárbol del hijo de $p$ en el que está $h_1$, o bien en el que está $h_2$. Si está en el mismo que $h_1$, luego el camino hasta $h_2$ va de $H$ a $p$, y de $p$ a $h_2$. Pero desde $H$ hasta $p$ hay una distancia mayor que desde $h_1$ hasta $p$, porque $H$ está más abajo. Es análogo si está en el mismo subárbol que $h_2$.

Entonces, llegamos a un absurdo por suponer que existe un nodo $H$ de mayor altura que ambas $h_1$ y $h_2$.

Conclusión: Uno de los extremos del diámetro del árbol es una de las hojas de mayor altura.

Como en principio no tenemos una raíz, pero para esto no nos importaba cuál fuera la raíz, basta con setear una raíz cualquier y encontrar el nodo más alejado. Éste nodo que encontremos será seguro un extremo del diámetro.

¿Y una vez que tenemos uno de los extremos? Fácil, simplemente buscamos el nodo que esté a mayor distancia de éste, con por ejemplo un BFS que ya conocemos.

Entonces el algoritmo que nos encuentra el diámetro (y sus extremos) del árbol es solamente poner un nodo cualquiera como raíz, buscar el más alejado (con un bfs por ejemplo). Y luego buscar el más alejado a este (con otro bfs).

El código queda así:

int main(){
    // Tenemos el grafo en un "vector< vector<int> > grafo"
    vector<bool> visitado(grafo.size(), false);
 
    queue<pair<int,int> > q;
    q.push(make_pair(0,0)); // empiezo como si el 0 fuera raíz, con una distancia 0 hasta la misma
    visitado[0]=true;
 
    int maxDistancia=0;
    int nodoMasAlejado;
 
    while(!q.empty()){
        pair<int,int> parActual = q.front();
        int nodoActual=parActual.first;
        int distancia=parActual.second;
        q.pop();
        if(distancia>maxDistancia){
            maxDistancia=distancia;
            nodoMasAlejado=nodoActual;
        }
        for(int i=0; i<grafo[nodoActual].size(); i++){
            if(!visitado[grafo[nodoActual][i]]){
                visitado[grafo[nodoActual][i]]=true;
                q.push(make_pair(grafo[nodoActual][i], distancia+1));
            }
        }
    }
    //Ahora q esta empty, repetimos lo mismo empezando desde el nodo mas alejado
 
    forn(i, visitado.size()){
        visitado[i]=false;
    }
    q.push(make_pair(nodoMasAlejado, 0));
    visitado[nodoMasAlejado]=true;
 
    int diametro=0;
    int otroExtremo;
    while(!q.empty()){
        pair<int,int> parActual = q.front();
        int nodoActual=parActual.first;
        int distancia=parActual.second;
        q.pop();
        if(distancia>diametro){
            diametro=distancia;
            otroExtremo=nodoActual;
        }
        for(int i=0; i<grafo[nodoActual].size(); i++){
            if(!visitado[grafo[nodoActual][i]]){
                visitado[grafo[nodoActual][i]]=true;
                q.push(make_pair(grafo[nodoActual][i], distancia+1));
            }
        }
    }
}

Lo que podríamos hacer también es una función que dado un nodo, nos devuelva un par ordenado con el nodo más alejado al dado, y la distancia entre ellos. Entonces simplemente llamamos a la función con el nodo $0$ (por ejemplo, cualquier raíz que seteemos al principio), y después de vuelta con el nodo obtenido como el más alejado al $0$.

El problema de encontrar el diámetro, también lo podemos resolver con programación dinámica en el árbol.

¿Cómo?

Pensemos que para cada nodo $u$, definimos $haciaAbajo(u)$ como la mayor distancia desde $u$ hacia abajo, es decir, entre $u$ y el nodo de mayor altura del subárbol $u$; y definimos $masLargo(u)$ como el camino más largo contenido en el subárbol de $u$ que pasa $u$, que en general va a venir desde uno de sus hijos y continuar hacia otro de ellos.

Para calcular $haciaAbajo(u)$, simplemente hacemos $1$ más la mayor distancia desde uno de sus hijos hacia abajo, recursivamente. Con caso base en una hoja, donde vale $0$.

Y para calcular $masLargo(u)$, lo que haremos será pensar, qué dos hijos me conviene que estén en el camino, para que lo más largo posible? Y, los hijos $v_1$ y $v_2$ que maximizen sus valores de $haciaAbajo$.

El siguiente código ilustra esta idea:

const int MAXN=1e5;
 
vector<int> haciaAbajo(MAXN), masLargo(MAXN);
int diametro=0;
 
void recorroSubarbol(int nodo, int padre){
    vector<int> hijosHaciaAbajo;
    for(int i=0; i<grafo[nodo].size(); i++){
        if(grafo[nodo][i]!=padre){
            int hijo=grafo[nodo][i];
            recorroSubarbol(hijo, nodo);
            hijosHaciaAbajo.push_back(haciaAbajo[hijo]);
        }
    }
    sort(hijosHaciaAbajo.begin(), hijosHaciaAbajo.end());
    int cantHijos=hijosHaciaAbajo.size();
    int miHaciaAbajo=1;
    if(cantHijos){
        miHaciaAbajo+=hijosHaciaAbajo[cantHijos-1];
    }
    int masLargoPasandoPorMi=0;
    if(cantHijos>=2){
        masLargoPasandoPorMi=2+hijosHaciaAbajo[cantHijos-1]+hijosHaciaAbajo[cantHijos-2];
    }
    haciaAbajo[nodo]=miHaciaAbajo;
    masLargo[nodo]=masLargoPasandoPorMi;
    diametro=max(diametro, max(masLargo[nodo], haciaAbajo[nodo]));
}
 
//Llamamos a recorroSubarbol(0, -1), seteando al 0 como raiz. En diametro queda el valor

http://codeforces.com/contest/911/problem/F

Agregar problemas!