#PU1016. USACO 2020 February Contest, Silver — Problem 3. Clock Tree

    ID: 1162 传统题 文件IO:clocktree 2000ms 256MiB 尝试: 0 已通过: 0 难度: 提高 上传者: 标签>USACO赛事:feb20来源:usaco.orgscoring:equal_test_cases树形DP深搜

USACO 2020 February Contest, Silver — Problem 3. Clock Tree

USACO 2020 February Contest, Silver — Problem 3. Clock Tree

题目描述

Farmer John's new barn has a truly strange design: it consists of NN rooms

(2≤N≤25002 \leq N \leq 2500), conveniently numbered 1…N1 \ldots N, and N−1N-1 corridors.

Each corridor connects a pair of rooms, in such a way that it is possible to

walk from any room to any other room along a series of corridors.

Every room in the barn has a circular clock on the wall with the standard

integers 1…121 \ldots 12 around its face. However, these clocks only have one

hand, which always points directly at one of the integers on the clock face (it

never points between two of these integers).

Bessie the cow wants to synchronize all the clocks in the barn so they all point

to the integer 12. However, she is somewhat simple-minded, and as she walks

around the barn, every time she enters a room, she moves the hand on its clock

ahead by one position. For example, if the clock pointed at 5, it would now

point at 6, and if the clock pointed at 12, it would now point at 1. If Bessie

enters the same room multiple times, she advances the clock in that room every

time she enters.

Please determine the number of rooms in which Bessie could start walking around

the barn such that she could conceivably set all the clocks to point to 12.

输入格式

The first line of input contains NN. The next line contains NN integers, each

in the range 1…121 \ldots 12, specifying the initial clock setting in each room.

The next N−1N-1 lines each describe a corridor in terms of two integers aa and

bb, each in the range 1…N1 \ldots N, giving the room numbers connected by the

corridor.

输出格式

Print the number of rooms in which Bessie could start, such that it is possible

for her to set all clocks to point to 12.

数据范围

Test cases 2-7 satisfy N≤100N\le 100.

Test cases 8-15 satisfy no additional constraints.

样例

样例 1

4

11 10 11 11

1 2

2 3

2 4
1

In this example, Bessie can set all the clocks to point to 12 if and only if she starts

in room 2 (for example, by moving to room 1, 2, 3, 2, and finally 4).

Problem credits: Brian Dean

提示

she would advance the clock in that room any time she re-entered it. Clocks do

not advance on their own; a clock only advances if Bessie enters its room.

Furthermore, once Bessie enters a corridor she must exit through the other end

(it is not allowed to walk partially through the corridor and loop back around

to the same room).