Las emociones de Teto#12449
Teto está componiendo una canción.
La canción puede representarse como un árbol con fragmentos. Cada fragmento es un vértice del árbol, y las aristas muestran cómo están conectados los fragmentos entre sí. Para cada fragmento , se da su valor emocional a_i.
Teto debe elegir exactamente un fragmento como fragmento central de la canción.
Después de eso, se eliminan de la canción todos los fragmentos cuya distancia desde es exactamente . También se eliminan todas las aristas incidentes a estos fragmentos.
El fragmento elegido no se elimina.
Después de la eliminación, el árbol puede dividirse en varias componentes conexas. Para cada una de estas componentes, calculamos la suma de los valores emocionales de todos los fragmentos que quedan en ella.
Sean estas sumas c_1, c_2, \ldots, c_k, donde es el número de componentes conexas después de la eliminación.
El contraste de elegir el fragmento se define como el valor , donde
D = \max(c_1, c_2, \ldots, c_k) - \min(c_1, c_2, \ldots, c_k).
Encuentra el máximo contraste posible entre todas las formas de elegir el fragmento central .
La primera línea contiene un entero (1 \le n \le 2 \cdot 10^5) — el número de fragmentos de la canción.
La segunda línea contiene enteros a_1, a_2, \ldots, a_n (-10^9 \le a_i \le 10^9) — los valores emocionales de los fragmentos.
Cada una de las siguientes n-1 líneas contiene dos enteros y (1 \le u, v \le n,\ u \ne v) — una arista del árbol.
Se garantiza que el grafo dado es un árbol.
Imprime un solo entero — el máximo contraste posible entre todas las elecciones del fragmento central .
Ejemplo 1
Ejemplo 2
En el primer ejemplo, es óptimo elegir el fragmento v = 4 como fragmento central. Entonces el fragmento está a distancia exactamente de él, por lo que se elimina.
Después de la eliminación, quedan dos componentes conexas:
con suma ;
\{3, 4, 5\} con suma 3 + 4 + 5 = 12.
Por lo tanto, el contraste es 12 - 1 = 11.
En el segundo ejemplo, es óptimo elegir el fragmento v = 2 como fragmento central. Entonces el fragmento está a distancia exactamente de él, por lo que se elimina.
Después de la eliminación, quedan tres componentes conexas:
\{1, 2, 4, 5\} con suma 5 + (-2) + 10 + (-3) = 10;
con suma ;
con suma .
Por lo tanto, el contraste es 10 - (-6) = 16.
Subtarea ( puntos): n \le 10.
Subtarea ( puntos): n \le 5000.
Subtarea ( puntos): el árbol es un camino.
Subtarea ( puntos): a_i = 1 para todo 1 \le i \le n.
Subtarea ( puntos): |a_i| \le 1 para todo 1 \le i \le n.
Subtarea ( puntos): a_i \ge 0 para todo 1 \le i \le n.
Subtarea ( puntos): Sin restricciones adicionales.