← Volver a los ejercicios

El valor de cada estación, UVa 10765

El valor paloma de una estación es en cuántos pedazos queda la red al bombardearla, que es cuántas palomas hacen falta para que un mensaje llegue a todas las estaciones que siguen en pie. Al quitar un vértice se desprende un pedazo por cada hijo w con low[w] ≥ d[u], y queda además el pedazo que sigue pegado al padre. La raíz no tiene padre: su valor es el número de hijos. La profundidad ya corrió y cada vértice trae su d/low.

1. La red con la profundidad hecha

Red:

━ arista del árbol ┅ arista de retroceso sobre cada vértice, d/low

Las estaciones van de 0 a n−1 y la profundidad arranca en la 0, recorriendo los vecinos de menor a mayor.

¿Cuál es el valor paloma más alto de esta red?

2. Escoja el valor de cada estación

Para cada vértice que no es la raíz, el valor arranca en 1 y suma un hijo por cada low[w] ≥ d[u]. La comparación admite la igualdad: si el subárbol de w vuelve a u pero no sube más, quitar u lo deja aparte igual.

3. Quite una estación y cuente

La definición ejecutada: se bombardea una estación y el dibujo recolorea los pedazos que quedan.

4. La salida que pide el juez

Las estaciones de mayor valor, ordenadas por valor decreciente y, a igual valor, por número creciente. Las parejas se arman como (-valor, v) y se ordenan de forma corriente: el signo invierte el primer campo y deja el segundo como está.

LíneaSalePor qué va ahí

La tabla se llena al comprobar los valores de arriba.

5. Para llevarse

Sin solución aquí. En la segunda red, agregue una vía entre la estación de mayor valor y la que está más lejos de ella en el árbol, y diga cuántos valores cambian. Después, en la tercera, corra la profundidad desde la estación 2 en lugar de la 0: los d y los low cambian, y la que era raíz deja de serlo. ¿Cambia algún valor paloma? Y por último: encuentre en alguna de las tres redes un vértice cuyo valor sea 2 sin que ninguna de sus vías sea puente, y explique con d y low por qué pasa.