题目描述

给定一棵以 $1$ 节点为根的树。每个节点上都被染了一种颜色，不同颜色用不同整数表示。

问：有多少个节点，它们到根节点的路径上的所有点（除了自己）的颜色都与自己的颜色不同。

输入格式

第一行输入整数 $n$（$2\le n\le 10^5$）。

第二行输入 $n$ 个整数，第 $i$ 个整数表示节点 $i$ 的颜色。（$1\le$ 每个节点的颜色 $\le 10^5$）

最后 $(n-1)$ 行：每行两个数 $a_i$,$b_i$，表示一条树边。

输出格式

输出若干行，一行一个整数，题目所求。输出时按照点的编号从小到大排序后输出。

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

1
2
3
4
6

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

1
2
3
5
6
7
8

样例 1 解释

如图所示，$5$ 号点到根的路径一共经过了 $5\to 2\to 1$ 这三个点，它们三个点的颜色分别是 $2,7,2$，其中 $1$ 的颜色与 $5$ 相同。因此 $5$ 不符合要求。