Dado un árbol binario con n nodos, cada nodo tiene un valor entero y está identificado con un valor entre 1 y n. Usted puede dividir el árbol en 2 partes (separando solamente un subarbol) y luego sumar los nodos que quedan en cada parte del árbol. Su tarea consiste en encontrar el mejor corte posible de tal manera que se minimice la resta en valor absoluto de las 2 partes del árbol cortadas.

Veamos un ejemplo:

NOTA: Tenga en cuenta que debe va a medir la eficiencia de su algoritmo. Evite realizar cálculos repetitivos.

Entrada La primera línea es un número T que representa la cantidad de casos de prueba. Cada caso de prueba inicia con una línea con un entero n que representa el número de nodos del árbol. La segunda línea contiene n números que indican el valor de cada uno de los nodos. Las siguientes n-1 líneas contienen cada una 2 números a,b que indican que el nodo a está conectado al nodo b. Los nodos se encuentran enumerados de 1 hasta n.

Restricciones/Consideraciones

2 < n < 100000

Salida Por cada caso debe imprimir la mínima diferencia entre las 2 partes.