# 1928 - Jogo da Memória
- **ID**: 1928
- **IdBecrowd**: 1928
- **Tags**: ad-hoc, geometria, grafos
- **Nível**: 9
- **Tempo Limite**: 2 segundos
- **Memória**: 200 MB
- **Categoria**: Grafos
- **Autor**: Maratona de Programacao da SBC

## Descrição
Pedro e Paulo resolveram complicar um pouco o tradicional Jogo da Memória, em que os jogadores precisam virar duas cartas iguais. Eles colocam 
N
 cartas no chão, com as faces viradas para baixo. A face de cada carta tem a figura de um número de 1 até 
N
/2, sendo que exatamente duas cartas possuem a figura de cada número entre 1 e 
N
/2. Como as cartas têm as faces viradas para baixo, elas podem também ser identificadas por suas posições, que são inteiros de 1 a 
N
. Pedro e Paulo então desenham no chão, usando giz, algumas linhas ligando pares de cartas, de modo que para qualquer par de cartas (
A, B
) existe uma e apenas uma sequência de cartas e linhas desenhadas que leva de 
A
 até 
B
. A figura abaixo mostra um exemplo de jogo, (a) com todas as cartas com as faces viradas para baixo, e (b) com todas as cartas com as faces viradas para cima.

![](assets/images/1fc3af_UOJ_1928_a.png)

![](assets/images/c89bf6_UOJ_1928_b.png)

O jogo é jogado com todas as cartas com as faces viradas para baixo. A cada jogada, o jogador deve escolher um par de cartas 
A
 e 
B
. Se as faces das duas cartas escolhidas têm a mesma figura, o jogador acumula um número de pontos igual ao número de linhas desenhadas que existem no caminho entre as cartas 
A
 e 
B
. Pedro e Paulo, agora, estão estudando qual é a melhor estratégia para esse jogo e precisam da sua ajuda para resolver uma tarefa específica: dadas as cartas existentes em cada posição, e as ligações desenhadas com giz, calcular o maior valor total de pontos que é possível acumular.

## Entrada
A primeira linha da entrada contém o número de cartas N (2 ≤ 
N
 ≤ 50000, 
N
 é par). A segunda linha da entrada contém 
N
 inteiros 
C
i
,
 indicando qual número está anotado na carta na posição i (1 ≤ 
C
i
 ≤ 
N
/2, para 1 ≤ 
i
 ≤ 
N
). As cartas são dadas na ordem crescente das posições: a primeira carta ocupa a posição 1, a segunda a posição 2, e assim por diante até a última carta, que ocupa a posição 
N
. Cada uma das 
N
 − 1 linhas seguintes contém dois números A e B, indicando que existe uma linha desenhada entre as cartas nas posições 
A
 e 
B
 (1 ≤ 
A
 ≤ 
N
 e 1 ≤ 
B
 ≤ 
N
).

## Saída
Seu programa deve produzir uma linha contendo um inteiro, o maior valor total de pontos que é possível acumular.

## Exemplos
### Exemplo de Entrada
```
6

                                3 2 1 1 2 3

                                1 2

                                3 4

                                6 5

                                2 6

                                3 6
```

### Exemplo de Saída
```
5
```