Problema F - Festa de Aniversário

O David vai festejar o seu aniversário e decidiu convidar alguns dos empregados da sua empresa, da qual ele é o diretor executivo (o CEO).

Cada empregado, incluindo o David, é identificado por um número entre 1 e N, um tipo V_i de piadas que sabe contar. Além disso, cada empregado (excepto o David) tem exatamente um supervisor. Como o David é o CEO, ele tem identificador 1 e é direta ou indiretamente chefe de todos (ou seja, todos são seus subordinados).

Na festa de aniversário, existem certas regras que todos (incluindo o David) devem seguir:

• Não devem existir duas pessoas que contam o mesmo tipo de piadas.
• A pessoa X não pode ser convidada se o seu supervisor directo não for convidado também.
• A pessoa X não pode ser convidada se o conjunto formado pelo tipo de piadas contadas por X mais os tipos contados pelos empregados que são seus subordinados (direta ou indirectamente) não formar um conjunto de números consecutivos.

Os números de um conjunto são consecutivos se a diferença entre elementos adjacentes é 1 quando o conjunto está ordenado por ordem crescente, como por exemplo (3,1,2) ou (5,1,2,4,3).

O Problema

O David quer saber quantos conjuntos diferentes de piadas que ele pode ouvir na sua festa, se forem obedecidas as suas regras.

Input

A primeira linha de input contém inteiros N, o número de pessoas da empresa (incluindo o David).

A segunda linha contém N inteiros V_i, os tipos de piada que cada trabalhador conta.

Cada uma das N-1 linhas seguintes contém dois inteiros: A e B, indicando que a pessoa A é um supervisor directo de B (ou seja, que B é um subordinado directo de A).

Output

Uma linha contendo um inteiro, a quantidade de diferentes conjuntos de piadas que obedecem aos requisitos atrás descritos.

Restrições

São garantidos os seguintes limites em todos os casos de teste que irão ser colocados ao programa:

Os casos de teste deste problema estão organizados em 2 grupos com restrições adicionais diferentes:

Input de Exemplo 1

4
2 1 3 4
1 2
1 3
3 4

Output de Exemplo 1

6

Explicação do Exemplo 1

É possível ter os seguintes conjuntos de piadas na festa: {2}, {2,3}, {2,3,4}, {1,2,3,4}, {1,2}, {1,2,3}.

Input de Exemplo 2

4
3 4 5 6
1 2
1 3
2 4

Output de Exemplo 2

3

Explicação do Exemplo 2

Os únicos conjuntos possíveis são {3}, {3,4} e {3,4,5}. Nota que a pessoa que conta a piada 6 não pode estar na festa porque, nesse caso, o conjunto de piadas {4,6} não é um conjunto de números consecutivos

Input de Exemplo 3

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

Output de Exemplo 3

10