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:

S is non-empty.

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.

.

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.

Examples

Input

Copy

1 4

2 1 3 2

1 2

1 3

3 4

Output

Input

Copy

0 3

1 2 3

1 2

2 3

Output

Input

Copy

4 8

7 8 7 5 4 6 4 10

1 6

1 2

5 8

1 3

3 5

6 7

3 4

Output

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.

题解

直接统计不好统计，所以考虑把方案分类。

按照最大值点对方案分类，枚举一个最大值点，让这一个点在方案中，这样就确定了方案能包含的连通块。

设\(dp[i]\)表示一定包含i这个点且i这个点是方案中权值最大的点的方案，有

\[dp[i] = \prod (dp[son_i] + 1)
\]

这样会计算重。因为最大值点所确定的连通块里，可能有多个与最大值点权值相同的点，每个点都会算一遍。

只算一个，然后乘以连通的相同值点的个数？

不！别忘了我们\(dp\)的时候，要求选定的点必须在方案中。必定包含不同的相同最大权值点的方案并不是一一对应的。

怎么办？

继续把方案分类。

在这个包含多个最大值点的极大连通块里，设有\(k\)个相同的最大值点。

设最大的相同点编号为\(x\)，\(dp\)必定包含点x的集合就行了。

这就相当于，我们只走比他编号小的相同权值的点。

两次使用最大值分类方案的神题Orz

被long long 和 MOD卡了两次。。

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <algorithm>

#include <map>

#include <cmath>

inline long long max(long long a, long long b){return a > b ? a : b;}

inline long long min(long long a, long long b){return a < b ? a : b;}

inline long long abs(long long x){return x < 0 ? -x : x;}

inline void swap(long long &x, long long &y){long long tmp = x;x = y;y = tmp;}

inline void read(long long &x)

{

    x = 0;char ch = getchar(), c = ch;

    while(ch < '0' || ch > '9') c = ch, ch = getchar();

    while(ch <= '9' && ch >= '0') x = x * 10 + ch - '0', ch = getchar();

    if(c == '-') x = -x;

}

const long long INF = 0x3f3f3f3f;

const long long MAXN = 2000 + 10;

const long long MOD = 1000000007;

struct Edge

{

	long long u,v,nxt;

	Edge(long long _u, long long _v, long long _nxt){u = _u, v  =_v, nxt = _nxt;}

	Edge(){}

}edge[MAXN << 1];

long long head[MAXN], cnt, n, val[MAXN], d, dp[MAXN], ans;

inline void insert(long long a, long long b)

{

	edge[++ cnt] = Edge(a, b, head[a]), head[a] = cnt;

}

void dfs(long long x, long long pre, long long root)

{

	dp[x] = 1;

	for(long long pos = head[x];pos;pos = edge[pos].nxt)

	{

		long long v = edge[pos].v;

		if(v == pre || val[root] - val[v] < 0 || val[root] - val[v] > d || (val[v] == val[root] && v > root)) continue;

		dfs(v, x, root);

		dp[x] *= (dp[v] + 1), dp[x] %= MOD;

	}

}

int main()

{

	read(d), read(n);

	for(long long i = 1;i <= n;++ i) read(val[i]);

    for(long long i = 1;i < n;++ i)

    {

    	long long tmp1, tmp2;

    	read(tmp1), read(tmp2);

    	insert(tmp1, tmp2), insert(tmp2, tmp1);

	}

	for(long long i = 1;i <= n;++ i)

	{

		memset(dp, 0, sizeof(dp));

		dfs(i, -1, i);

		ans += dp[i] % MOD;

		if(ans >= MOD) ans -= MOD;

	}

	printf("%I64d", ans);

	return 0;

}

巴特西

Codeforces 486D. Valid Sets

D. Valid Sets

Input

Output

Examples

Input

Output

Input

Output

Input

Output

Note

题解

最新文章

热门文章