Jogo da memória
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 N. A segunda linha da entrada contém N inteiros C_i, 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, 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.Restrições
- 2 ≤ N ≤ 50000, N é par
- 1 ≤ C_i ≤ N/2
- 1 ≤ A ≤ N e 1 ≤ B ≤ N
Informações sobre a Pontuação
- Em um conjunto de casos de teste valendo 50 pontos, N ≤ 1000
Exemplos
Entrada
6 2 2 1 1 3 3 1 2 3 4 6 5 2 6 3 6 |
Saída
3 |
Entrada
8 1 2 3 3 2 4 1 4 1 2 2 3 2 6 5 6 6 8 7 8 4 7 |
Saída
12 |
