Codeforces Round #277 (Div. 2)D (tree DP counting class)_html/css_WEB-ITnose

D. Valid Sets

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

As you know, an undirected connected graph with n nodes and n?-?1 edges is called a tree. You are given an integer d and a tree consisting of n nodes. Each node i has a value ai associated with it.

We call a set S of tree nodes valid if following conditions are satisfied:

1. S is non-empty.
2. S is connected. In other words, if nodes u and v are in S, then all nodes lying on the simple path between u and v should also be presented in S.
3. .

Your task is to count the number of valid sets. Since the result can be very large, you must print its remainder modulo 1000000007(109? ?7).

Input

The first line contains two space-separated integers d (0?≤?d?≤?2000) and n (1?≤?n?≤?2000).

The second line contains n space-separated positive integers a1,?a2,?...,?an(1?≤?ai?≤?2000).

Then the next n?-?1 line each contain pair of integers u and v (1?≤?u,?v?≤?n) denoting that there is an edge between u and v. It is guaranteed that these edges form a tree.

Output

Print the number of valid sets modulo 1000000007.

Sample test(s)

input

1 42 1 3 21 21 33 4

output

input

0 31 2 31 22 3

output

input

4 87 8 7 5 4 6 4 101 61 25 81 33 56 73 4

output

41

Note

In the first sample, there are exactly 8 valid sets: {1},?{2},?{3},?{4},?{1,?2},?{1,?3},?{3,?4} and {1,?3,?4}. Set {1,?2,?3,?4} is not valid, because the third condition isn't satisfied. Set {1,?4} satisfies the third condition, but conflicts with the second condition.

题意：RT

思路：树形DP，dp[u]表示以u为根，且它的所有子树的点v的权值都不超过它，且满足 w[u]-w[v]<=d 的方案数

            对于每个点为根这样算一遍就好了，注意减去算重的情况，即相邻多个点的权值相等，可以用点的代号去重（即规定只能从代号大的往小的DP）