Mansão do Luigi 4

Luigi recebeu uma carta misteriosa que, por coincidência, abriu no dia 6 de junho de 2026, às 06:06:06.666666666.

Obbobobo Boobo,

Boobobob obbobbobbo boo o bbobób bo bo obóbobo bobbobobobób ob ob BOO BBOBB BBOB BBOBOB, bo bobobo obo bobboób obobbobo bo 2000 bobbob boobbobob bobobobbob b 20000 bobbob boobbobob ob bobob.
Ob ob bobob bboboo ob bo bobboboo bo obbo bobbobbo; boobo, bob bobbob bob obbob 4 bobob boo bo bo bobobo ¡Bobo bo bobobob boo obbo bob bo ob obo bbobbo bobbob!

Bo bobboób boobbo bob bobo bo boboboboo, bobbo obo boobbo bobbo obo bobo bo bobo bobo boo boo bob bobóbobob bo bobbob bobobobob. Bo obbobobob obbobobbo.
OBBB bobbobobobbob, obbobo boo bo bobob bobbobo boobbo bobobbo obbo bobbo.
Obbo,
Bob Boo

Luigi não sabe ler Boogio, mas sabe muito bem do que se trata.

— Devo ter ganhado uma mansão de novo!

E, como já o enganaram três vezes com mansões, é impossível que a quarta também seja um engano. Luigi tomou a decisão de aceitar o prêmio e viajou imediatamente para a mansão.

Chegando lá, já do lado de dentro, o Rei Boo lhe disse “Hahahahaha, era uma armadilha, você jamais conseguirá sair desta mansão” e depois desapareceu sem deixar rastro. Luigi tentou sair, mas não conseguiu.

Dentro do cômodo há um mapa da mansão, e Luigi rapidamente percebeu que existe apenas uma forma de ir de qualquer cômodo a outro, e que é possível ir a qualquer cômodo a partir do cômodo em que ele se encontra.

A mansão tem $n$ cômodos e cada cômodo tem uma lâmpada. O Rei Boo deixou algumas acesas e outras apagadas. Para não passar a noite no escuro entre fantasmas, Luigi quer deixar todas acesas usando a menor quantidade possível de movimentos.

Mas Luigi é um medroso terrível: toda vez que entra correndo em um cômodo, com o susto ele bate no interruptor e a lâmpada desse cômodo se inverte: uma acesa se apaga e uma apagada se acende. Parado em um cômodo, Luigi pode fazer uma destas duas coisas, e cada uma conta como um movimento:

• correr para um cômodo vizinho e, ao entrar correndo, inverter a lâmpada desse cômodo;

• acalmar-se e inverter a lâmpada do cômodo onde está.

Antes de Luigi começar a se mover, de algum lugar do cômodo em que se encontra ele consegue ouvir o professor E. Gadd: “Luigi, tudo o que posso fazer para ajudá-lo é teletransportá-lo para o seu cômodo preferido uma única vez; você aparecerá lá sem que a lâmpada desse cômodo mude”.

Luigi deve decidir onde começar, e não importa onde ele termine. Qual é o número mínimo de movimentos para deixar todas as lâmpadas acesas?

Entrada

A primeira linha contém um inteiro $n$: a quantidade de cômodos ($1 \leq n \leq 2 \cdot 10^5$).

A segunda linha contém $n$ inteiros $c_1, \ldots, c_n$, onde $c_i = 1$ se a lâmpada do cômodo $i$ está acesa e $c_i = 0$ se está apagada.

Cada uma das $n - 1$ linhas seguintes contém dois inteiros $u_i$ e $v_i$ ($1 \leq u_i, v_i \leq n$, $u_i \neq v_i$): um corredor que liga os cômodos $u_i$ e $v_i$. Garante-se que é possível visitar todos os cômodos a partir do cômodo $1$, e que há um único caminho de um cômodo a outro.

Saída

Imprima um único inteiro: o número mínimo de movimentos para acender todas as lâmpadas.

3
0 1 0
1 2
2 3

4

5
1 0 0 0 0
1 2
1 3
1 4
1 5

8