14902번 - 트리 분해

문제

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

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

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

입력

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

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

출력

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

제한

힌트

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

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