Lo siento, permítanme comenzar con esto diciendo que generalmente no hago esto, por lo que la explicación puede ser aproximada y puede ser incorrecta, pero creo que las ideas deberían ser modificables a la solución. También partes de esto se vuelven más simples con la búsqueda binaria si NlgN está bien.
Considere todos los bordes como el posible eliminado:
Arregla la raíz del árbol. Para cada borde, al eliminarlo, se divide en 2 subárboles. El nuevo borde óptimo conecta los centros de los 2 subárboles. Intente eliminar bordes como dfs desde la raíz. Esto reduce la cuestión de encontrar los centros / radios y el diámetro de todos los subárboles, así como mantener esto para el barrido DFS hacia abajo.
Subárboles:
El diámetro es un DP estándar. Centro / radios es más molesto. Se basa en que el centro se puede encontrar moviéndolo constantemente hacia el subárbol con la ruta más larga (ver más abajo). Afirmo que puede mantener el centro en lineal mirando el subárbol que tiene el camino más largo hacia una hoja. Como ya conocemos el centro de ese subárbol y el nuevo centro tiene que estar en el camino desde ese centro hasta la raíz de nuestro subárbol actual: deberíamos poder moverlo hacia arriba hasta que sea el nuevo centro. Así que sigue moviéndote mientras lo comparas con la segunda ruta más larga desde la nueva raíz. Esto debería ser O (N) total ya que no se visita ningún nodo más de una vez.
Para DFS hacia abajo:
El diámetro es fácil. Radii nuevamente: voy a afirmar que el centro de un árbol siempre estará en algún diámetro, específicamente cerca del punto medio de uno. Prueba: cualquier cosa que no esté en el diámetro tiene una peor distancia a uno de los puntos finales del diámetro, y en el diámetro uno de los puntos medios es el mejor. Entonces, si arraigamos el árbol en uno de los nodos del diámetro, podemos mantener que el diámetro siempre está en la parte superior del barrido. Ahora, si nuestro borde de corte no está en el diámetro, ya conocemos los radios. De lo contrario: podemos hacer exactamente lo mismo para los subárboles, moviendo lentamente el centro hacia adelante. Como siempre está en una línea fija, será O (N) máx.
Radios partes:
Un algoritmo para encontrar el radio / centro de un árbol es elegir un nodo aleatorio y observar las rutas más largas a una hoja en todos los subárboles que son hijos de ese nodo. Luego, elija al niño en el subárbol con el camino más largo. Esto se modifica para funcionar para esta pregunta.
Resumen:
1) Encuentra el diámetro del árbol. Fijar la raíz en algún lugar de diámetro. EN)
2) Buscar para todos los nodos: longitud de ese nodo a una hoja en su subárbol, la más larga de estas longitudes (y qué hijo) para todos los hijos y lo mismo para el segundo más largo. Alternativamente, solo encuentre esta información para todos y ordene con countort. EN)
3) Encuentra el diámetro de todos los subárboles. EN)
4) Encuentra el centro de todos los subárboles. Tome el centro del subárbol con la longitud más larga (que se encuentra arriba). Mueva el centro hacia arriba (llame donde está actualmente: c) siempre que la ruta de c a nuestra raíz + segunda ruta más larga sea> la ruta más larga del subárbol de c. O (N) amortizado ya que no se visita ningún nodo más de una vez.
5) Barrer hacia abajo. Mantener el diámetro O (N)
6) Para todos los cortes no en diámetro. El radio es conocido, no es un problema.
7) De lo contrario, encuentre el centro de partida asumiendo que los cortes están en el diámetro. Muévelo más cerca de 4 a medida que nos movemos al
Perdón por el boceto.
