AT_abc198_e [ABC198E] Unique Color

题目描述

给定一棵以 $1$ 节点为根的树。每个节点上都被染了一种颜色，不同颜色用不同整数表示。问：有多少个节点，它们到根节点的路径上的所有点（除了自己）的颜色都与自己的颜色不同。

输入格式

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

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

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

输出格式

一行一个整数，题目所求。

样例 1

输入

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

输出

1
2
3
4
6

样例 2

输入

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