wjw 的彩虹树

题目描述

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