Clock Tree

题目描述

农夫约翰的新谷仓有一种非常奇怪的设计：它由 $N$ 个房间（$2 \leq N \leq 2500$）和 $N-1$ 条走廊组成。房间方便地编号为 $1 \ldots N$。每条走廊连接一对房间，使得可以沿着一系列走廊从任意房间走到任意其他房间。 谷仓中的每个房间墙上都有一个圆形时钟，表盘上有标准的整数 $1 \ldots 12$。不过这些时钟只有一根指针，并且指针总是恰好指向表盘上的某一个整数（不会指在两个整数之间）。 奶牛贝茜想把谷仓里所有时钟都同步到指向整数 12。然而她有点简单：当她在谷仓里走动时，每当她进入一个房间，就会把该房间时钟的指针向前拨动一格。例如，如果时钟指向 5，那么现在会指向 6；如果指向 12，那么现在会指向 1。如果贝茜多次进入同一个房间，她每次进入都会让该房间的时钟前进一格。 请确定：有多少个房间可以作为贝茜开始走动的起点，使得她有可能让所有时钟最终都指向 12。 注意：贝茜在起始房间一开始不会拨动该房间的时钟，但她之后每次重新进入该房间都会拨动。时钟不会自行前进；只有贝茜进入该房间时才会前进。此外，一旦贝茜进入一条走廊，她必须从另一端出去（不允许只走到走廊中途又返回到同一个房间）。

输入格式

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

输出格式

输出贝茜可以作为起点开始的房间数量，使得她有可能让所有时钟都指向 12。

4
11 10 11 11
1 2
2 3
2 4

1

提示

评分： 测试点 2-7 满足 $N\le 100$。 测试点 8-15 没有额外限制。

在这个例子中，当且仅当贝茜从房间 2 开始时，她可以把所有时钟都调到指向 12（例如，按顺序移动到房间 1、2、3、2，最后到 4）。 题目作者：Brian Dean

标签: USACO|2020|Silver

来源

USACO|2020|Silver