#6276. 果树

内存限制:512 MiB 时间限制:4000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: BigFairyNBC

题目描述

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

3
1 2 3
1 2
1 3

样例输出 1

6

样例输入 2

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

样例输出 2

8

样例解释 1

(1,1)(1,2)(1,3)(2,2)(2,3)(3,3) 6 条路径。

样例解释 2

(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 的特殊限制如下,不填代表该项无特殊限制。

Subtask 编号 N 其他限制 该 Subtask 分值
0 \le 100 12
1 \le 3000 25
2 整棵树形成一条依次为 1, 2, 3, \ldots , N 的链 30
3 33