Guaso el presidente


Submit solution

Points: 100 (partial)
Time limit: 2.0s
Memory limit: 512M

Author:
Problem types
Allowed languages
C++, Python

Descripción

¡El Casique Guaso se presenta a presidente de Guantánamo! En los debates, se le preguntará cómo resolver el problema de transporte de Guantanamo. Es un problema realmente difícil porque el sistema de transporte de Guantanamo es ahora un árbol (grafo conectado sin ciclos). El equipo de Guaso ha descubierto en el Ministerio de Transporte de Guantanamo que sólo hay dinero en el presupuesto para una carretera adicional. En los debates, va a decir que construirá esta carretera como forma de maximizar el número de caminos simples distintos en el país. Un camino simple es un camino que no pasa más de una vez por cada vértice. Dos caminos simples se denominan distintos si los conjuntos de sus aristas son distintos.

Pero la ciencia de Guantanamo está deteriorada, por lo que el equipo de Guaso no ha conseguido encontrar a ningún científico que responda cuántos caminos simples distintos pueden conseguir tras añadir exactamente una arista en el sistema de transporte.

Ayuda a Guaso a resolverlo.

Se puede añadir una arista entre vértices que ya están conectados, pero no puede ser un bucle.

En este problema, consideramos sólo caminos simples de longitud al menos dos.

Entrada

La primera línea contiene un número entero n (2 \le n \le 500 000) - número de vértices en el sistema de transporte de Guantanamo.

Cada una de las siguientes n-1 líneas contiene dos enteros v_i y u_i (1 \le v_i, u_i \le n). Se garantiza que el grafo es arborescente.

Salida

Imprime exactamente un entero - número máximo de caminos simples que se pueden conseguir después de añadir una arista.

Ejemplos

Entrada 1

2          
1 2

Salida 1

2

Entrada 2

4         
1 2
1 3
1 4

Salida 2

11

Entrada 3

6      
1 2
1 3
3 4
3 5
4 6

Salida 3

29

Comments

There are no comments at the moment.