$\color{red}\texttt{Z}\color{orange}\texttt{B}\color{green}\texttt{O}\color{cyan}\texttt{J}\color{black}-\texttt{P1007}$

$\texttt{Zyp's Colorful Tree}$

$\texttt{Description}$

某 $\texttt{hs}$ 完成了重默任务，和小 $\texttt{C}$ 到达了小树林。他们两个在这片树林的中心发现了一些彩色魔力树，这些树的每一个节点都是彩色的，它们是小姐姐 $\texttt{Zyp}$ 在若干年前栽下的。某 $\texttt{hs}$ 看到了这些漂亮的树，决定在最美丽的那棵树上刻下他和小 $\texttt{C}$ 的名字。可是这里的树实在是太高大了，导致某 $\texttt{hs}$ 无法在短时间内找到最美丽的树，现在他用某种方式联系到了你，你能帮帮他吗？

你的任务是对于某一棵彩色树，算出它的美丽值，最后的比较任务会由某 $\texttt{hs}$ 完成。一棵彩色树上有 $n$ 个节点，它的美丽值定义为树上任意两节点间的美丽值之和，即 $\frac{n(n-1)}{2}$ 对节点之间的美丽值之和。两节点间美丽值定义为两节点间最短路径上包含的所有节点（包括两个端点）的不同颜色数量。

$\texttt{Input Format}$

第一行一个数 $n$。第二行 $n$ 个整数表示每个节点的颜色 $c_i$。后 $n-1$ 行每行两个数 $u,v$，表示节点 $u$ 和节点 $v$ 间有一条连边。

$\texttt{Output Format}$

一个数表示答案。

$\texttt{Sample}$

$\texttt{Input 1}$

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

$\texttt{Output 1}$

xxxxxxxxxx
29

$\texttt{Hint}$

对于 $100\%$ 的数据，满足 $n\leq 200000,1\leq c_i\leq 500000$。