CF486D Valid Sets

如你所知，一个包含 $n$ 个节点和 $n-1$ 条边的无向连通图被称为树。现在给定一个整数 $d$ 以及一棵有 $n$ 个节点的树。每个节点 $i$ 有一个属性值 $a_i$。 我们称树节点的一个集合 $S$ 是合法的，如果满足以下条件： 1. $S$ 非空。 2. $S$ 是连通的。换句话说，若节点 $u$ 和 $v$ 都在 $S$ 中，则 $u$ 到 $v$ 的唯一路径上的所有节点也都在 $S$ 中。 3. $S$ 中所有节点的 $a_i$ 的最大值与最小值之差不超过 $d$，即 $\max_{i \in S} a_i - \min_{i \in S} a_i \le d$。 你的任务是计算合法集合的数目。由于结果可能非常大，请输出对 $1000000007$（$10^9+7$）取模后的结果。

第一行包含两个用空格分隔的整数 $d$（$0 \le d \le 2000$）和 $n$（$1 \le n \le 2000$）。 第二行包含 $n$ 个用空格隔开的正整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 2000$）。 接下来 $n-1$ 行，每行包含两个整数 $u$ 和 $v$（$1 \le u, v \le n$），表示在 $u$ 和 $v$ 间有一条边。保证这些边构成一棵树。

输出合法集合的个数，对 $1000000007$ 取模。

在第一个样例中，恰好有 8 个合法集合：$\{1\}$、$\{2\}$、$\{3\}$、$\{4\}$、$\{1,2\}$、$\{1,3\}$、$\{3,4\}$ 和 $\{1,3,4\}$。集合 $\{1,2,3,4\}$ 不合法，因为不满足第三个条件。集合 $\{1,4\}$ 虽然满足第三个条件，但不连通，不满足第二个条件。 由 ChatGPT 5 翻译