Inversiones en un árbol#13094
Se te da un árbol con vértices numerados de a . El árbol está enraizado en el vértice .
Cada vértice tiene una etiqueta p_i. Todas las etiquetas son distintas y forman una permutación de los enteros de a .
Una inversión es un par de vértices que cumple ambas condiciones:
El vértice es un ancestro estricto del vértice , es decir, u \ne v y se encuentra en el camino desde la raíz hasta .
p_u > p_v.
Puedes realizar a lo sumo una operación: elegir cualquier arista e intercambiar las etiquetas de sus extremos. La estructura del árbol no cambia.
Halla la máxima cantidad posible de inversiones después de realizar a lo sumo una operación.
La primera línea contiene un entero (1 \leq n \leq 2 \cdot 10^5) — la cantidad de vértices.
La segunda línea contiene enteros p_1,p_2,\ldots,p_n (1 \leq p_i \leq n) — las etiquetas. Todos estos números son distintos.
Cada una de las siguientes n-1 líneas contiene dos enteros y (1 \leq u,v \leq n, u \ne v), que describen una arista del árbol.
Se garantiza que el grafo dado es un árbol.
Imprime un entero — la máxima cantidad posible de inversiones.
Ejemplo 1
Ejemplo 2
Ejemplo 3
En el primer ejemplo, el árbol consta de un solo vértice. No hay inversiones y no es posible realizar ninguna operación. Por lo tanto, la respuesta es .
En el segundo ejemplo, se intercambian las etiquetas de los vértices y . Entonces el vértice contiene y los otros cuatro vértices contienen etiquetas menores. Como el vértice es ancestro de todos ellos, hay inversiones. No es posible obtener un valor mayor.
En el tercer ejemplo, los vértices forman el camino ––– con las etiquetas 4,3,2,1. Todo par de vértices distintos es una inversión, lo que da inversiones en total. Esta ya es la cantidad máxima para cuatro vértices, así que no se necesita ninguna operación.
puntos — 1 \leq n \leq 10.
puntos — el árbol es una estrella con centro en el vértice .
puntos — el árbol es un camino simple que tiene al vértice como uno de sus extremos.
puntos — 1 \leq n \leq 3000.
puntos — sin restricciones adicionales.