URI Online Judge | 2470

Jogo da Memória

Por OBI - Olimpíada Brasileira de Informática 2014 BR Brazil

Timelimit: 1

Pedro e Paulo resolveram complicar um pouco o tradicional Jogo da Memória, em que os jogadores precisam virar duas cartas iguais. Eles colocam as cartas no chão, viradas para baixo, e fazem algumas linhas ligando pares de cartas, usando giz, de modo que para qualquer par de cartas (A, B) existe uma e apenas uma sequência de cartas distintas que leva de A até B através das linhas que eles desenharam. Com isso, ao virar duas cartas, o jogador ganha uma quantidade de pontos igual ao tamanho da sequência de linhas entre as duas cartas, se elas forem iguais. Se forem diferentes, o jogador perde aquela quantidade de pontos.

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 ligações entre as N cartas, calcular a soma dos tamanhos das sequências entre todos os N/2 pares de cartas iguais!

O jogo possui N cartas, de índices 1 até N. Cada carta possui a figura de um número de 1 até N/2 desenhada. Exatamente duas cartas possuem a figura de cada número entre 1 e N/2.

Entrada

A primeira linha da entrada contém o número de cartas (2 ≤ N ≤ 50000, N é par). A segunda linha da entrada contém N inteiros Ci (1 ≤ CiN/2) , 1 ≤ iN, indicando qual número está anotado na carta de índice i. Cada uma das N −1 linhas seguintes contém dois números A e B (1 ≤ A, BN), indicando que existe uma linha desenhada entre as cartas de índices A e B.

Saída

Seu programa deve imprimir uma linha contendo um inteiro, a soma dos tamanhos das sequências entre todos os N/2 pares de cartas iguais.

Exemplos de Entrada Exemplos de Saída

6
2 2 1 1 3 3
1 2
3 4
6 5
2 6
3 6

3

8
1 2 3 3 2 4 1 4
1 2
2 3
2 6
5 6
6 8
7 8
4 7

12