CF1467E.Distinctive Roots in a Tree

You are given a tree with $n$ vertices. Each vertex $i$ has a value $a_i$ associated with it.

Let us root the tree at some vertex $v$. The vertex $v$ is called a distinctive root if the following holds: in all paths that start at $v$ and end at some other node, all the values encountered are distinct. Two different paths may have values in common but a single path must have all distinct values.

Find the number of distinctive roots in the tree.

给你一棵包含 $n$ 个顶点的树。每个顶点 $i$ 关联一个值 $a_i$。

我们以某个顶点 $v$ 为根对树进行定根。若顶点 $v$ 满足如下条件，则称其为特征根：所有从 $v$ 出发、终止于其他任意节点的路径上，所经过的所有顶点的值互不相同。不同路径之间可以有重复的值，但单条路径上的所有值必须互异。

请计算该树中特征根的个数。

The first line of the input contains a single integer $n$ ($1 \le n \le 2\cdot10^5$) — the number of vertices in the tree.

The next line contains $n$ space-separated integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$).

The following $n-1$ lines each contain two space-separated integers $u$ and $v$ ($1 \le u$, $v \le n$), denoting an edge from $u$ to $v$.

It is guaranteed that the edges form a tree.

输入的第一行包含一个整数 $n$（$1 \le n \le 2\cdot10^5$）——树中顶点的数量。

第二行包含 $n$ 个用空格分隔的整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^9$）。

接下来的 $n-1$ 行每行包含两个用空格分隔的整数 $u$ 和 $v$（$1 \le u, v \le n$），表示一条从 $u$ 到 $v$ 的边。

保证这些边构成一棵树。

Print a single integer — the number of distinctive roots in the tree.

输出一个整数——树中不同根的数量。

In the first example, $1$, $2$ and $5$ are distinctive roots.

在第一个例子中，$1$、$2$ 和 $5$ 是互异的根。