Cable de respaldo#13117
En un país hay ciudades conectadas por n-1 carreteras bidireccionales. Entre cualesquiera dos ciudades existe exactamente un camino simple.
Para que la red de carreteras sea más fiable, se construirá exactamente una nueva carretera entre dos ciudades distintas que aún no estén conectadas directamente.
Después de la construcción se consideran n-1 escenarios de fallo independientes. En el escenario deja de estar disponible únicamente la -ésima carretera original. Todas las demás carreteras, incluida la nueva, siguen disponibles. La red se restaura antes de cada escenario.
Llamamos daño causado por un fallo a la cantidad de ciudades que quedan fuera de la mayor componente conexa después de eliminar la carretera correspondiente. Si todas las ciudades siguen conectadas, el daño es cero.
Elija la nueva carretera de modo que la suma de los daños sobre los n-1 escenarios sea mínima. Encuentre esta suma mínima.
La primera línea contiene un entero (3\le n\le 2\cdot10^5) — la cantidad de ciudades.
Cada una de las siguientes n-1 líneas contiene dos enteros u_i,v_i (1\le u_i,v_i\le n, u_i\ne v_i) — los extremos de la -ésima carretera original.
Se garantiza que la red original de carreteras es un árbol.
Imprima un entero — la mínima suma posible de daños después de construir una nueva carretera.
Ejemplo 1
Ejemplo 2
Ejemplo 3
En el primer ejemplo se puede construir una carretera entre las ciudades y . Entonces el fallo de cualquier carretera original deja la red conexa, por lo que la respuesta es .
En el segundo ejemplo se puede construir una carretera entre las ciudades y . Los fallos de las carreteras y no desconectan la red, mientras que el fallo de la carretera aísla una ciudad. El daño total es .
En el tercer ejemplo la nueva carretera solo puede proteger dos carreteras originales. Cada uno de los otros dos fallos aísla una ciudad, por lo que la respuesta es .
Subtarea ( puntos): n\le 9.
Subtarea ( puntos): n\le 100.
Subtarea ( puntos): n\le 2000.
Subtarea ( puntos): a lo sumo una ciudad está conectada directamente por carreteras originales con más de dos ciudades.
Subtarea ( puntos): sin restricciones adicionales.