树上求和

题目描述 给一棵�个节点的树，第�个节点有一个颜色��。

请问对于树上所有点对 �, � 1 ≤ � < � ≤ � ，它们路径上的点有多少种不同的颜 色。输出所有点对的答案的和。

输入格式 第一行，一个整数�，表示节点个数。

接下来一行，一共�个整数�1 , �2 , …, �� ，表示每个点的颜色。

接下来� − 1 行，每行两个数�, �，表示树上的一条边。

输出格式 一行，一个整数，表示答案。

样例输入 1 6 1 2 1 3 2 1 1 2 1 3 2 4 2 5 3 6

样例输出 1 29

样例输入输出 2 见下发文件。

数据规模 共 10 组数据。

测试点 1 满足� ≤ 100。

测试点 2,3 满足� ≤ 103 。

测试点 4,5 满足� ≤ 2 × 105 , 1 ≤ �� ≤ 20。

测试点 6,7 满足� ≤ 2 × 105 ，每种颜色节点数不超过 20 个。

对于 100%数据，满足 1 ≤ � ≤ 2 × 105 , 1 ≤ �� ≤ �。