题目描述

这里有一棵有 $n$ 个点的树，每一个树上的节点有一个权值，即为 $v_i$，以 $1$ 为根，点以 $1\sim n$ 编号。

现在，我们想从选出一些点，并满足以下条件：

1. 一个点的父亲点若未被选择则其不能被选择。
2. 所选点的集合内不能有相同的权值。
3. 对于每一个选择的点，其子树中所有被选择点的权值必须可以构成公差为 $1$ 的等差数列。

您只需要输出满足上述条件的方案个数。

注意：这里的方案指所选的数的集合不同的方案。

输入格式

第一行为一个整数 $n$。

接下来一行 $n$ 个整数 $v_i$。

接下来 $n-1$ 行，一行两个整数 $a_i,b_i$，第 $i$ 行描述树上有一条以 $a_i$ 为父亲，$b_i$ 为儿子的边。

输出格式

仅一行一个整数，表示满足上述条件的方案个数。

4
2 1 3 4
1 2
1 3
3 4 

6

4
3 4 5 6
1 2
1 3
2 4

3

6
5 3 6 4 2 1
1 2
1 3
1 4
2 5
5 6 

10

提示

【样例解释】

样例 1 解释

如下为选点的权值的六种情况：

$\{2\},\{2,3\},\{2,3,4\},\{1,2,3,4\},\{1,2\},\{1,2,3\}$。

样例 2 解释

如下为选点的权值的三种情况：

$\{3\},\{3,4\},\{3,4,5\}$。

注意到不能选权值为 $6$ 的点，因为其父亲点与其构成的子树 $\{4,6\}$ 不符条件。

【数据范围及限制】

• 对于 $50\%$ 的数据，保证 $n\le 100$。
• 对于 $100\%$ 的数据，保证 $1\le n\le 10^4$，$1\le v_i\le 100$，$1\le a_i,b_i\le n$。

【说明】

本题满分 $160$ 分。

本题译自 Croatian Open Competition in Informatics 2015/2016 Contest #1 T6 UZASTOPNI。