Jogo da Memória
Por OBI - Olimpíada Brasileira de Informática 2014 
Brazil
Por OBI - Olimpíada Brasileira de Informática 2014 Brazil
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.
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 Ci (1 ≤ Ci ≤ N/2) , 1 ≤ i ≤ N, 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, B ≤ N), indicando que existe uma linha desenhada entre as cartas de índices A e B.
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 |
3 |
|
8 |
12 |