题目描述

NiroBC 姐姐是个活泼的少女，她十分喜欢爬树，而她家门口正好有一棵果树，正好满足了她爬树的需求。

这颗果树有 $N$ 个节点，标号 $1 \ldots N$ 。每个节点长着一个果子，第 $i$ 个节点上的果子颜色为 $C_i$ 。

NiroBC 姐姐每天都要爬树，每天都要选择一条有趣的路径 $(u, v)$ 来爬。

一条路径被称作有趣的，当且仅当这条路径上的果子的颜色互不相同。

$(u, v)$ 和 $(v, u)$ 被视作同一条路径。特殊地， $(i, i)$ 也被视作一条路径，这条路径只含 $i$ 一个节点，显然是有趣的。

NiroBC 姐姐想知道这颗树上有多少条有趣的路径。

输入格式

第一行，一个整数 $N$ ，表示果树的节点数目。

接下来一行 $N$ 个整数 $C_{1 \ldots N}$ ，表示 $N$ 个果子各自的颜色。

再接下来 $N-1$ 行，每行两个整数 $u_i, v_i$ ，表示 $u_i$ 和 $v_i$ 之间有一条边。

数据保证这 $N-1$ 条边构成一棵树。

输出格式

一个整数，有趣的路径的数量。

样例 1

input

3
1 2 3
1 2
1 3

output

6

样例 2

input

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

output

8

有 $(1,1)(1,2)(1,3)(2,2)(2,3)(3,3)$ 共 $6$ 条路径。

有 $(1,1)(1,3)(2,2)(2,4)(2,5)(3,3)(4,4)(5,5)$ 共 $8$ 条路径。

数据范围与提示

对于所有数据， $1 \le N \le 10^5$ ，$ 1 \le C_i \le N$ ，每种颜色在树上出现不超过 $20$ 次。

本题采用打包测试。

各个 Subtask 的特殊限制如下，不填代表该项无特殊限制。