TAP2016K - Koalas

no tags 

[Due to SPOJ restrictions, this problem has been modified with respect to the original version used in the Argentinian Programming Tournament of 2016 in order to have multiple test cases per input file. The original version of this problem (in Spanish) can be found at http://torneoprogramacion.com.ar/wp-content/uploads/2016/09/tap2016.pdf ]

 

Mabel Eucaliptos ha pasado toda la noche entren\'andose en el arte de comer hojas de eucalipto. Finalmente est\'a preparada para enfrentar a su malvada archin\'emesis, Pac\'ifica, en un \'ultimo juego que intentar\'a decidir de una vez por todas qui\'en de las dos es la mejor koala.
El juego se llevar\'a a cabo en un bosque constituido por $N$ \'arboles de eucalipto numerados del $1$ al $N$. Los \'arboles est\'an conectados por $N - 1$ cuerdas. Cada cuerda conecta dos \'arboles diferentes, y permite a las koalas desplazarse de cualquiera de ellos al otro. El bosque de eucaliptos es tal que es posible ir de cualquier \'arbol a cualquier otro usando sucesivamente estas cuerdas.
Los \'arboles de eucalipto contienen una cantidad no negativa de hojas. Cuando un \'arbol contiene cero hojas, se dice que est\'a vac\'io. Inicialmente ninguno de los $N$ \'arboles en los que se desarrollar\'a el juego se encuentra vac\'io.
Antes de empezar el juego, a cada koala se le asigna un \'arbol diferente. Al principio de la partida cada jugadora sube al \'arbol que le fue asignado y come todas las hojas que este contiene, dej\'andolo vac\'io. A continuaci\'on, juegan alternadamente, siendo Mabel la encargada de realizar el primer movimiento. En cada turno la jugadora correspondiente se mueve a un \'arbol no vac\'io que est\'e conectado por una cuerda con el \'arbol en el que se encuentra ella. Seguidamente come todas las hojas que este nuevo \'arbol contiene, dej\'andolo vac\'io. En caso de no poder realizar un movimiento v\'alido, permanece donde est\'a y pasa a ser el turno de la otra jugadora. El juego termina cuando ninguna de las dos puede hacer un movimiento v\'alido.
Una vez finalizada la partida, se cuentan las hojas que comi\'o cada koala, y se calcula la diferencia entre la cantidad que comi\'o Mabel y la cantidad que comi\'o Pac\'ifica. Mabel jugar\'a tratando de maximizar dicha diferencia, mientras que Pac\'ifica lo har\'a intentando minimizarla. Su tarea es determinar cu\'al ser\'a el resultado del juego, suponiendo que ambas juegan de manera \'optima.

Mabel Eucalyptus spent last night training in the art of eucalyptus leaf eating. She is finally ready to face her evil arch-nemesis, Peaceful, in a last game which will decide once and for all which of them is the best koala.

The game will take place in a forest containing N eucalyptus trees numbered from 1 to N. The trees are connected by N-1 ropes, each of which joins two different trees. These ropes allow koalas to move from one tree to the other, and the eucalyptus forest is such that it is possible to go from a given tree to any other successively using the ropes.

The eucalyptus trees contain a non-negative amount of leaves. When a tree contains no leaves, we say it is empty. Initially, none of the N trees in the forest is empty.

Before commencing the game, each koala is assigned a different tree. At the beginning of the game, each player climbs the tree that was assigned to her and eats all the leaves it contains. After that both players take turns, Mabel being in charge of making the first move. In each turn, the corresponding player moves to a non-empty tree connected by a rope to the tree she is currently in. Then, she eats all the leaves this tree contains, thus leaving it empty. If a player can't make a valid move in her turn, she forfeits her turn staying wherever she is, and the other player gets to move again. The game ends when both players cannot make a valid move.

Once the game has finished, the number of leaves eaten by each koala is counted, and the difference between the amount eaten by Mabel and the amount eaten by Peaceful is calculated. Mabel will play aiming to maximize this difference, whereas Peaceful will play to minimize it. Your task is to determine what the result of the game will be, assuming that both koalas play optimally.

 

Input

There are multiple test cases in the input file. For each test case, the first line contains three integer numbers N, M y P, representing the number of trees in the forest, the tree where Mabel starts, and the tree where Peaceful starts, respectively (2 ≤ N  105 and  M, P  N with M ≠ P). The second line contains N integer numbers C1, C2, ..., CN, representing Ci the number of leaves contained in the i-th tree ( Ci  100 for i = 1, 2, ..., N). Each of the following N-1 lines contains two integer numbers U and V, representing that there is a rope connecting trees number U and V ( U, V  N with U ≠ V).

 

Output

For each test case, output a single line containing an integer number, representing the difference between the number of leaves eaten by Mabel and the number of leaves eaten by Peaceful if both of them play optimally.

 

Example

Input:
2 1 2
5 3
1 2
6 2 3
1 6 4 3 2 2
1 2
2 3
3 4
3 5
5 6

Output:
2
-1


Added by:Fidel Schaposnik
Date:2016-09-21
Time limit:3s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU
Resource:Argentinian Programming Tournament 2016