3356. [USACO20 Feb Silver]Clock Tree

【题目描述】

Farmer John 的新牛棚的设计十分奇怪：它由编号为 $1 \ldots N$ 的 $N$ 间房间（$2 \leq N \leq 2500$），以及 $N-1$ 条走廊组成。每条走廊连接两间房间，使得每间房间都可以沿着一些走廊到达任意其他房间。

牛棚里的每间房间都装有一个在表盘上印有标准的整数 $1 \ldots 12$ 的圆形时钟。然而，这些时钟只有一根指针，并且总是直接指向表盘上的某个数字（它从不指向两个数字之间）。

奶牛 Bessie 想要同步牛棚中的所有时钟，使它们都指向整数 12。然而，她头脑稍有些简单，当她在牛棚里行走的时候，每次她进入一间房间，她将房间里的时钟的指针向后拨动一个位置。例如，如果原来时钟指向 5，现在它会指向 6，如果原来时钟指向 12，现在它会指向 1。如果 Bessie 进入同一间房间多次，她每次进入都会拨动这间房间的时钟。

请求出 Bessie 可能的出发房间数量，使得她可以在牛棚中走动并使所有时钟指向 12。注意 Bessie 并不拨动她出发房间的时钟，但任意时刻她再次进入的时候会拨动它。时钟不会自己走动；时钟只会在 Bessie 进入时被拨动。此外，Bessie 一旦进入了一条走廊，她必须到达走廊的另一端（不允许走到一半折回原来的房间）。

【输入格式】

输入的第一行包含 $N$。下一行包含 $N$ 个整数，均在范围 $1 \ldots 12$ 之内，表示每间房间初始时的时钟设置。以下 $N-1$ 行每行用两个整数 $a$ 和 $b$ 描述了一条走廊，两数均在范围 $1 \ldots N$ 之内，为该走廊连接的两间房间的编号。

【输出格式】

输出出发房间的数量，使得 Bessie 有可能使所有时钟指向 12。

【样例输入】

4
11 10 11 11
1 2
2 3
2 4

【样例输出】

1

【样例解释】

在这个例子中，当且仅当 Bessie 从房间 2 出发时她可以使所有房间的时钟指向 12（比如，移动到房间 1，2，3，2，最后到 4）。

【提示】

对于$ 47\% $的测试数据(测试点$ 1 \sim 7 $)，满足$ N ≤ 100 $。 

对于$ 100\% $的测试数据，均满足上文所给出的数据规模。

【来源】

USACO 二月公开赛 Silver 组