#P1467E. Distinctive Roots in a Tree
-
ID: 5722
Type: RemoteJudge
3000ms
256MiB
Tried: 0
Accepted: 0
Difficulty: (None)
Uploaded By:
Hydro
Tags> Distinctive Roots in a Tree
No submission language available for this problem.
Description
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.
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.
Print a single integer — the number of distinctive roots in the tree.
Input
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.
Output
Print a single integer — the number of distinctive roots in the tree.
Samples
5
2 5 1 1 4
1 2
1 3
2 4
2 5
3
5
2 1 1 1 4
1 2
1 3
2 4
2 5
0
Note
In the first example, $1$, $2$ and $5$ are distinctive roots.