Hay un árbol $T=(V,E)$ con $N$ vértices. Cada vértice tiene escrito un entero; ten en cuenta que puede ser negativo. Queremos encontrar dos subgrafos $T_a=(V_a,E_a)$ y $T_b=(V_b,E_b)$ de $T$ que cumplan las siguientes condiciones.

• $V_a\ne\varnothing,\quad V_b\ne\varnothing$

• $T_a$ y $T_b$ son conexos.

• $V_a\cap V_b=\varnothing$

• No hay ninguna arista en $E$ que una un vértice de $V_a$ con uno de $V_b$.

• La suma de los enteros escritos en los vértices de $V_a$ y los escritos en los vértices de $V_b$ debe ser lo mayor posible.

Considera el ejemplo de la siguiente figura. $T=(\{0,1,2,3,4,5,6\},\{(0,1),(0,2),(2,3),(2,4),(4,6),(5,6)\})$.

Los números encima de los vértices son sus etiquetas y los de dentro son sus valores. Puede haber varias elecciones de $T_a,T_b$ que cumplan las condiciones. Tomando $V_a=\{0,2,3\}$ y $V_b=\{5,6\}$, se obtiene la suma máxima $\{3+(-1)+4\}+\{5+3\}=14$. Hay otras elecciones, pero ninguna da un valor mayor que $14$.

Debes implementar la siguiente función.

long long findSum( int N, int C[], int Node1[], int Node2[] );

Esta función se llama exactamente una vez. La entrada se pasa mediante argumentos y el valor devuelto es la respuesta. $N$ es el número de vértices, numerados del $0$ al $N-1$. Para $0\le i\le N-1$, C[i] es el entero escrito en el vértice $i$. Para $0\le i\le N-2$, hay una arista entre los vértices Node1[i] y Node2[i].

Detalles de implementación

Debes enviar exactamente un archivo llamado tree.cpp que implemente la siguiente función.

long long findSum( int N, int C[], int Node1[], int Node2[] );

La función debe comportarse como se ha descrito. Puedes definir otras funciones para uso interno. El código enviado no debe realizar entrada/salida ni acceder a otros archivos.

Evaluador de ejemplo

El evaluador proporcionado lee la entrada con el siguiente formato.

• Línea 1: $N$

• Línea 2: $N$ enteros $C_0,C_1,\ldots,C_{N-1}$, los valores de los vértices en orden.

• Las siguientes $N-1$ líneas: dos enteros $a,b$ que indican una arista entre los vértices $a$ y $b$.

Ten cuidado: si después del carácter que representa el último dígito de una línea hay espacios u otros caracteres, el evaluador podría no funcionar correctamente.

El evaluador imprime el valor devuelto por tu función findSum().

Restricciones

• $-10^9\le C_i\le10^9$

• $3\le N\le500,000$

Subtareas

1. (7 puntos) $N\le20$

2. (19 puntos) $N\le5000$

3. (74 puntos) Sin restricciones adicionales.

Ejemplos

Entrada 1

7
3 -5 -1 4 2 5 3
0 1
0 2
2 3
2 4
4 6
5 6

Salida 1

14