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 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 Ci , 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 ≤ Ci ≤ N/2
• 1≤A≤N e1≤B≤N
| Exemplos de Entrada | Exemplos de Saída |
|---|---|
|
6 |
3 |
Efetue Login ou Cadastre-se para submeter uma solução.
Adaptado por erich.rodriguesf | Competição: OBI 2014, Nível 1, Fase 2