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.

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