시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 0 0 0 0.000%

문제

루트 없는 트리가 주어진다. 트리의 각 노드에는 정수가 쓰여져 있다.

트리를 경로의 집합으로 분해하는 방법의 수를 구하는 프로그램을 작성하시오. 분해했을 때, 나온 경로는 아래 조건을 만족해야 한다.

  • 모든 노드는 하나의 경로에 속해야 한다.
  • 각 경로에 속한 노드에 써 있는 정수의 합은 음이 아닌 정수이어야 한다.

입력

첫째 줄에 N(1 ≤ N ≤ 105)가 주어진다. 둘째 줄에는 정점에 써 있는 정수가 1번 정점부터 순서대로 주어진다. 각 정수는 절대값이 104보다 작거나 같은 정수이다.

셋째 줄부터 N-1개의 줄에는 트리의 간선을 나타내는 두 정점이 주어진다.

출력

첫째 줄에 문제의 조건을 지키면서 트리를 분할하는 방법의 수를 109+7로 나눈 나머지를 출력한다.

예제 입력

4
1 10 5 -1
1 2
1 3
2 4

예제 출력

4

힌트

예제의 경우 4가지 방법이 가능하다.

  • 트리는 하나의 경로로 이루어져 있기 때문에, 전체 트리도 트리를 분할하는 하나의 방법이다. 이 때, 경로의 합은 1+10+5+(-1) = 15이기 때문에, 음이 아닌 정수라는 문제의 조건도 만족한다.
  • 첫 번째 경로는 2와 4를 연결하는 경로, 나머지는 1과 3을 연결하는 경로로 나누는 방법이다. 첫 번째 경로는 10+(-1) = 9, 두 번째 경로 1+5 = 6으로 합이 음이 아닌 정수이다.
  • 첫 번째 경로는 1, 2, 4를 연결하는 경로, 나머지 경로는 3만 존재하는 경로로 나누는 방법이다.
  • 한 경로는 2, 4를 연결하는 경로, 다른 하나는 1, 세 번째는 3으로 나눌 수 있다.

출처