一个公司有N个员工，编号从1到N，每一个员工都有一个上级，除了1号CEO，他是其所有他人的直接或间接上级。公司总共有V种笑话，用数值Vi表示。
生日宴会上出席有这些规则：
1.不能有两个人有相同的笑话。
2.如果一个人的直接上级没有出席则他不能出席。
3. 以一个人为根的子树中，所有的笑话集合如果不连续，则它的子树不能被选。
现在请计算有多少种不同的出席情况
Input
第一行一个数N（1<=N<=10000）
第二行N个数，第i个数表示第i个人的笑话的值，Vi(1<=Vi<=100)
接下来N-1 行，两个整数A和B（1<=A,B<=N）,表示A是B的直接上级。
Output
一个数，表示不同的集合的个数。
50%的数据N<=100

input
4
2 1 3 4
1 2
1 3
3 4
output
6
input
4
3 4 5 6
1 2
1 3
2 4
output
3
input
6
5 3 6 4 2 1
1 2
1 3
1 4
2 5
5 6
output
10