[USACO20FEB] Clock Tree S
题目描述
Farmer John 的新牛棚的设计十分奇怪:它由编号为 $1\ldots N$ 的 $N$ 间房间($2\leq N\leq 2\,500$),以及 $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$。
输入输出样例
输入样例 #1
4
11 10 11 11
1 2
2 3
2 4
输出样例 #1
1
说明
#### 样例解释:
在这个例子中,当且仅当 Bessie 从房间 $2$ 出发时她可以使所有房间的时钟指向 $12$(比如,移动到房间 $1$,$2$,$3$,$2$,最后到 $4$)。
#### 子任务:
- 测试点 $2$-$7$ 满足 $N\leq 100$。
- 测试点 $8$-$15$ 没有额外限制。