Informatica Online Judge

  서브트리의 수 [1143 / 0477]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 17   Total Tried : 236


The Champion of this Problem (C++) : N/A
My Best Submission (C++) : N/A

[Codeforces]

Background

여러분은 트리에 대해서 잘 알고 있을 것이다.

n개의 노드를 n-1개의 선으로 연결한 연결 그래프를 트리라고 한다.

여러분에게 하나의 트리와 d라는 값이 주어진다.

각 트리의 노드는 a_i 라는 값을 가지고 있다.

다음과 같은 조건을 만족하는 서브트리 S 들을 구하고자 한다.

1. S는 공집합이 아니다.
2. S는 연결그래프이다.
3. S의 임의의 노드 u, v에 대해서 max a_u - min a_v <= d 이다.
(즉, S의 노드중 가장 큰 값과 가장 작은 값의 차이는 d이하이다.)

여러분은 주어진 그래프에서 위 조건을 만족하는 서브트리 S의 개수를 세는 프로그램을 작성해야 한다. 단, 수가 너무 많을 수 있으므로 1,000,000,007 로 나눈 나머지를 출력한다.

Input

첫 번째 줄에 d와 n이 공백으로 구분되어 입력된다.
두 번째 줄에 n개의 정수가 공백으로 구분되어 입력된다. 이 값은 각 노드의 a_i 값을 의미한다.
세번째 줄부터 n-1줄에 걸쳐서 선이 연결하고 있는 2개의 노드가 입력된다.

[입력값의 정의역]
1 <= d, n, a_i <= 2,000

Output

조건을 만족하는 S의 수를 10억 7로 나눈 나머지를 출력한다.

IO Example

입력
1 4
2 1 3 2
1 2
1 3
3 4

출력
8

*설명 : 가능한 S 는 정점의 번호를 집합으로 볼 때, {1}, {2}, {3}, {4}, {1, 2}, {1, 3}, {3, 4}, {1, 3, 4}로 모두 8개이다. {1, 2, 3, 4}는 d값이 1을 초과하므로 조건에 만족하지 않는다.

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]