题目描述

本题译自 COCI 2015-2016 Contest #1 T6「UZASTOPNI」。

这里有一棵有 $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

数据范围与提示

• 对于 $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$。