Description

The design of Farmer John's new barn is quite strange: it consists of $N$ rooms numbered $1\ldots N$ ($2\leq N\leq 2\,500$), and $N-1$ hallways. Each hallway connects two rooms, so that every room can reach any other room by following some sequence of hallways.

Each room in the barn contains a round clock whose face has the standard integers $1\ldots 12$ printed on it. However, these clocks have only one hand, and it always points directly at one of the numbers on the face (it never points between two numbers).

The cow Bessie wants to synchronize all the clocks in the barn so that they all point to the integer $12$. However, she is not very smart: as she walks around the barn, every time she enters a room, she moves the clock hand in that room back by one position. For example, if the clock was pointing to $5$, it will now point to $6$; if it was pointing to $12$, it will now point to $1$. If Bessie enters the same room multiple times, she moves that room's clock each time she enters.

Compute the number of possible starting rooms such that Bessie can walk around the barn and make all clocks point to $12$. Note that Bessie does not move the clock in her starting room, but any time she enters it again later, she will move it. The clocks do not run on their own; a clock changes only when Bessie enters its room. Also, once Bessie enters a hallway, she must reach the other end of the hallway (she is not allowed to turn back halfway and return to the original room).

Input Format

The first line contains $N$. The next line contains $N$ integers, each in the range $1\ldots 12$, describing the initial clock setting in each room. The following $N-1$ lines each contain two integers $a$ and $b$, both in the range $1\ldots N$, describing a hallway connecting rooms $a$ and $b$.

Output Format

Output the number of starting rooms such that it is possible for Bessie to make all clocks point to $12$.

4
11 10 11 11
1 2
2 3
2 4

1

Hint

Sample Explanation:

In this example, Bessie can make all the clocks point to $12$ if and only if she starts from room $2$ (for example, by moving to rooms $1$, $2$, $3$, $2$, and finally $4$).

Subtasks:

• Test cases $2$-$7$ satisfy $N\leq 100$.
• Test cases $8$-$15$ have no additional constraints.

Translated by ChatGPT 5