时空限制

2S/512M

题目描述

给定一棵有 $n$ 个顶点的无根树，其中 $n$ 为偶数。每个顶点有一种颜色，每种颜色恰好出现两次。

你需要选择一个顶点 $r$ 作为树根。对于任意顶点 $u$，定义 $u$ 的深度为 $u$ 到 $r$ 的简单路径上的边数。

若对于每种颜色，该颜色对应的两个顶点深度不同，则称 $r$ 为一个合法的树根。

求合法树根的数量。

格式

输入格式

第一行包含一个正偶数 $n$，表示树的顶点数量。

第二行包含 $n$ 个正整数 $c_1,c_2,\ldots,c_n$，其中 $c_i$ 表示顶点 $i$ 的颜色。保证每个 $1\le x\le n/2$ 恰好在序列中出现两次。

接下来 $n-1$ 行，每行包含两个正整数 $u,v$，表示顶点 $u$ 与顶点 $v$ 之间有一条无向边。

保证输入的边构成一棵树。

输出格式

输出一行一个整数，表示合法树根的数量。

样例

样例输入 #1

4
1 2 1 2
1 2
2 3
2 4

样例输出 #1

2

样例解释 #1

选择顶点 $1$ 或顶点 $3$ 作为树根时，每种颜色的两个顶点深度均不同。选择顶点 $2$ 或顶点 $4$ 作为树根时，颜色 $1$ 对应的两个顶点深度相同。

样例输入 #2

8
1 2 3 3 4 2 1 4
1 2
2 3
3 4
4 5
5 6
6 7
7 8

样例输出 #2

7

样例输入 #3

10
5 3 4 5 1 2 1 3 4 2
2 1
3 2
4 1
5 1
6 2
7 5
8 6
9 5
10 2

样例输出 #3

2

数据规模

注意：你只有通过了子任务的所有测试点，才能获得对应子任务的分数。

子任务编号	分数	$n\le$	特殊性质
$1$	$30$	$2000$	无
$2$		$2\times 10^5$	特殊性质 A
$3$	$40$		无

特殊性质 A：对于任意 $1\le i<n$，顶点 $i$ 与顶点 $i+1$ 之间均有一条边。

对于 $100\%$ 的数据，满足 $2\le n\le 2\times 10^5$，$n$ 为偶数，$1\le c_i\le n/2$，每种颜色恰好出现两次，$1\le u,v\le n$，$u\ne v$，且输入的边构成一棵树。