Clock Synchronization in the Barn

Farmer John's new barn has a very peculiar design: it consists of N rooms numbered from \(1\) to \(N\) (with \(2 \leq N \leq 2500\)) connected by \(N-1\) corridors such that any room can be reached from any other room. Each room contains a circular clock with the numbers \(1,2,\ldots,12\) arranged on its dial. However, each clock has only one hand that always points exactly at one of the numbers (never between two numbers).

Bessie, one of the cows, would like to synchronize all the clocks so that they point to \(12\). When Bessie walks through the barn she has a very simple habit: every time she enters a room, she advances that room’s clock by one. (Note that if she re‐enters a room then she advances its clock again.) The only exception is the room she starts in – upon starting, she does not adjust that room’s clock. Once she has entered a corridor she must go all the way to the other end; she cannot turn back midway. Also, the clocks do not move on their own; they are advanced solely by Bessie’s entries into the rooms.

Your task is to determine how many different starting rooms exist for which Bessie can walk around the barn in such a way that, at the end, every clock shows \(12\). Formally, let the initial reading of room \(i\) be \(c_i\) \((1 \le c_i \le 12)\). When Bessie enters a room (other than the starting room, which does not count on her initial presence) its clock is advanced by 1 (modulo \(12\), where \(12+1\) becomes \(1\)). If a room is entered extra times, the clock is advanced that many extra times. Thus if room \(i\) is entered \(x_i\) times (not counting the starting presence) then the final reading is \((c_i + x_i) \bmod 12\) (where we treat \(12\) as \(0\) modulo \(12\)). For a starting room \(s\) the condition to achieve synchrony is:

[ \begin{cases} (c_s + \sum_{v\in child(s)}f(v)) \equiv 0 \pmod{12}, & \text{(starting room)}\ (c_u + 1 + \sum_{v\in child(u)}f(v)) \equiv 0 \pmod{12}, & \text{(for every other room }u\text{)} \end{cases} ]

We can show that a valid route exists if and only if the above system can be solved; your job is to count the number of starting rooms \(s\) for which a solution exists.

inputFormat

The first line contains a single integer \(N\) (\(2 \le N \le 2500\)).

The second line contains \(N\) space‐separated integers \(c_1, c_2, \ldots, c_N\) (each between 1 and 12) indicating the initial clock reading in each room.

The following \(N-1\) lines each contain two integers \(u\) and \(v\) (\(1 \le u,v \le N\)) indicating that there is a corridor connecting room \(u\) and room \(v\). It is guaranteed that the corridors connect the rooms so that any room is reachable from any other room.

outputFormat

Output a single integer: the number of rooms \(s\) (\(1 \le s \le N\)) for which there exists a route starting at \(s\) that eventually synchronizes all clocks to \(12\).

sample

3
11 11 11
1 2
2 3

0