Clock Tree

Farmer John's new barn has a truly unusual design: it consists of $N$ rooms ($2 \leq N \leq 2500$), numbered $1 \ldots N$, and $N-1$ corridors. Each corridor connects a pair of rooms, and it is possible to walk from any room to any other room along a series of corridors.

Every room has a circular clock on the wall with the standard integers $1 \ldots 12$ around its face. Each clock has only one hand, which always points directly at one of the integers, never between two of them.

Bessie the cow wants to set all the clocks in the barn to point to 12. She is somewhat simple-minded, though. Each time she enters a room, she moves the hand on that room's clock ahead by one position. For example, a clock pointing at 5 moves to 6, and a clock pointing at 12 moves to 1. If Bessie enters the same room several times, the clock advances every time she enters.

Determine the number of rooms where Bessie could start walking so that she can set all the clocks to point to 12. Bessie does not advance the clock in her starting room at the start, but she advances it whenever she re-enters that room. Clocks do not move on their own. A clock advances only when Bessie enters its room. Once Bessie enters a corridor, she must leave through its other end. She may not walk partway into a corridor and turn back.

The first line contains $N$. The next line contains $N$ integers, each from $1 \ldots 12$, giving the initial setting of each room's clock. Each of the next $N-1$ lines contains two integers $a$ and $b$, each from $1 \ldots N$, giving the rooms connected by a corridor.

Print the number of starting rooms from which Bessie can set all clocks to point to 12.

In this example, Bessie can set all the clocks to point to 12 if and only if she starts in room 2. For example, she can walk through rooms 1, 2, 3, 2, and finally 4.