#518. 「多校联考 Round 1」Ambitio

内存限制:512 MiB 时间限制:1000 ms 输入文件:ambitio.in 输出文件:ambitio.out
题目类型:传统 评测方式:文本比较
上传者: Woshiluo

题目描述

没有什么比彩灯更有节日气氛了。llt 准备了好多彩灯,来庆祝寰宇教育集团成立一周年纪念日。

现在有 n 个彩灯,每个彩灯都有一个颜色 a_i。彩灯已由 n-1 条线连接,保证任意两个彩灯之间互相联通。

定义一条路径是好的是指路径上没有任何两个彩灯颜色一样。

我们要选择一个彩灯作为中心点。定义一个好的中心点是指从这个彩灯为起点的所有路径都是好的。

llt 想知道一共有多少个彩灯可以作为中心点,使得这个中心点是好的。

输入格式

第一行一个整数 n

第二行 n 个整数 a_i

接下来 n-1 一行,每行两个整数 u,v,表示彩灯 u,v 相连。

输出格式

一行一个整数,表示答案。

样例

样例 1:

ambitio1.in:

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

ambitio1.ans:

3

样例 2:

ambitio2.in:

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

ambitio2.ans:

0

数据范围与提示

对于 30\% 的数据, 保证 n = 100

对于 70\% 的数据, 保证 n = 1000, a_i \leq 10^4

对于 100\% 的数据, 保证 n = 2 \times 10^5, 1 \leq a_i \leq 10^9