Existe uma árvore $T=(V,E)$ com $N$ vértices. Em cada vértice está escrito um inteiro, que pode ser negativo. Pretende-se encontrar dois subgrafos $T_a=(V_a,E_a)$ e $T_b=(V_b,E_b)$ de $T$ que satisfaçam as condições seguintes.

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

• $T_a$ e $T_b$ são ambos conexos.

• $V_a\cap V_b=\varnothing$

• Não existe em $E$ nenhuma aresta entre um vértice de $V_a$ e um vértice de $V_b$.

• A soma dos inteiros escritos nos vértices de $V_a$ com os escritos nos vértices de $V_b$ deve ser a maior possível.

Considere o exemplo na figura seguinte. $T=(\{0,1,2,3,4,5,6\},\{(0,1),(0,2),(2,3),(2,4),(4,6),(5,6)\})$.

Os números por cima dos vértices são os seus rótulos; os números no interior são os seus valores. Pode haver várias escolhas de $T_a,T_b$ que satisfaçam as condições. Escolher $V_a=\{0,2,3\}$ e $V_b=\{5,6\}$ dá a soma máxima $\{3+(-1)+4\}+\{5+3\}=14$. Existem outras escolhas, mas nenhuma permite obter um valor superior a $14$.

Deve implementar a função seguinte.

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

Esta função é chamada exatamente uma vez. A entrada é passada pelos argumentos e o valor devolvido é a resposta. $N$ é o número de vértices, numerados de $0$ a $N-1$. Para $0\le i\le N-1$, C[i] é o inteiro escrito no vértice $i$. Para $0\le i\le N-2$, existe uma aresta entre os vértices Node1[i] e Node2[i].

Detalhes de implementação

Deve submeter exatamente um ficheiro chamado tree.cpp, que implemente a função seguinte.

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

A função deve comportar-se como descrito acima. Pode definir outras funções para uso interno. O código submetido não deve efetuar entrada/saída nem aceder a outros ficheiros.

Avaliador de exemplo

O avaliador fornecido lê a entrada no formato seguinte.

• Linha 1: $N$

• Linha 2: $N$ inteiros $C_0,C_1,\ldots,C_{N-1}$, os valores dos vértices por ordem.

• As $N-1$ linhas seguintes: dois inteiros $a,b$ que indicam uma aresta entre os vértices $a$ e $b$.

Atenção: se existirem espaços ou outros caracteres depois do carácter que representa o último algarismo de uma linha, o avaliador pode não funcionar corretamente.

O avaliador imprime o valor devolvido pela sua função findSum().

Restrições

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

• $3\le N\le500,000$

Subtarefas

1. (7 pontos) $N\le20$

2. (19 pontos) $N\le5000$

3. (74 pontos) Sem restrições adicionais.

Exemplos

Entrada 1

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

Saída 1

14