该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

wjw 最近学习了树上路径的概念，于是他又画了一棵树来练习

但是他觉得一棵普通的树实在是太单调了，所以他给这棵有 $n$ 个节点的树的每个节点涂了颜色

现在 wjw 写了一个函数 sum_color(u,v) 这个函数可以计算出树上 $u->v$ 这条路径上有多少种不同的颜色

wjw 为了验证这个函数是否正确，他写了下面这段代码

int ans = 0;
for (int u = 1; u <= n; ++u){
	for (int v = u + 1; v <= n; ++v){
		ans += sum_color(u, v);
	}
}
cout << ans << endl;

现在他想知道对于一棵树，这份代码输出的正确答案应该是多少？

输入格式

第一行，一个整数 $n$，表示节点个数。 接下来一行，一共 $n$ 个整数 $c_1,c_2,c_3 \dots, c_n$，表示每个点的颜色。

接下来 $n − 1$ 行，每行两个数 $u,v$，表示树上的一条边

输出格式

输出一个数，表示这份代码输出的结果

数据范围

对于 $10\%$ 的数据，满足 $1 \leq n \leq 100$ 对于 $30\%$ 的数据，满足 $1 \leq n \leq 10^3$ 对于 $50\%$ 的数据，满足 $1 \leq c_i \leq 20$ 对于 $100\%$ 的数据，满足 $1 \leq n \leq 2 * 10^5, 1 \leq c_i \leq n$ 。

样例输入

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

样例输出

29