Morning Walk

Seohyun enjoys morning walks, and she wants to keep enjoying them after entering Seoul Science High School. She analyzed the school's layout for her walks, and found she could simplify it into a tree with $N$ places connected by $N-1$ paths. Because the structure is a tree, every place can be reached from every other place by way of some paths.

A morning walk is defined by choosing a start point and an end point, then walking along the simple path on the tree from the start point to the end point (a path that does not pass through the same point more than once). The path between two points on a tree is unique, so once the start point and end point are chosen, the path is determined uniquely.

Among the $N$ places, some are indoors and the rest are outdoors. Seohyun does not want to exercise before the walk starts, so both the start point and the end point of the walk must be indoors. Also, because seeing an indoor place during the walk makes her want to stop walking, there must be no indoor place on the walk path other than the start point and the end point.

Seohyun wants to walk a different route every day. Let us find how many distinct walk routes there are.

The first line gives the number of vertices $N$.

The second line gives a string $A$ of length $N$ consisting of 1s and 0s. If the $i$-th character $A_i$ is 1, place $i$ is indoors; if it is 0, place $i$ is outdoors.

From the third line to the $N+1$-th line, the $i+2$-th line gives two integers $u_i$, $v_i$ representing each edge of the tree. This means the $i$-th edge connects vertex $u_i$ and vertex $v_i$.

Print the number of possible distinct walk routes.

• $2 \le N \le 2 \times 10^5$
• $1 \le u_i , v_i \le N$
• $u_i \neq v_i$
• The input structure is guaranteed to form a valid tree.