Tree path decomposition

Time limit2sMemory limit512 MB

Summary

Count the ways to partition all nodes of an unrooted tree into vertex-disjoint paths, where each path's node sum is nonnegative, modulo 1e9+7.

Level: Hard8 of 10
Topics: Tree, Dynamic programming, DFS
Solved: No attempts yet

Problem

You are given a tree with no root. Each node has one integer written on it.

Write a program that counts the ways to decompose the tree into a set of paths. A decomposition has to satisfy both conditions below.

Every node belongs to exactly one path.
The sum of the integers written on the nodes of a path is nonnegative.

A path here is a subgraph whose nodes are joined one after another along the edges of the tree, and a path that holds a single node counts as a path. Two decompositions are different when they group the nodes differently.

Input

The first line contains the number of nodes $N$ ( $1 \le N \le 10^5$ ). The second line contains the integers written on node 1 through node $N$ , in that order. Each integer has absolute value at most $10^4$ .

Each of the next $N-1$ lines contains the numbers of the two nodes joined by an edge. The given graph is always a tree.

Output

Print the number of decompositions that satisfy the conditions, modulo $10^9+7$ .

Hint

The first example has four decompositions.

The whole tree is one path. Its sum is $1+10+5+(-1)=15$ , so it satisfies the condition.
One path joins nodes 2 and 4, the other joins nodes 1 and 3. The two sums are $10+(-1)=9$ and $1+5=6$ .
One path joins nodes 1, 2 and 4, and the other holds node 3 alone.
One path joins nodes 2 and 4, and the remaining two paths hold node 1 alone and node 3 alone.

Examples3

Example 1
Input
```
4
1 10 5 -1
1 2
1 3
2 4
```
Expected output
```
4
```
Example 2
Input
```
1
0
```
Expected output
```
1
```
Example 3
Input
```
1
-7
```
Expected output
```
0
```