레이팅 미적용농부 존의 새 헛간은 정말 이상한 구조를 가지고 있다. 헛간은 \(1 \ldots N\)으로 번호가 매겨진 \(N\)개의 방(\(2 \leq N \leq 2500\))과 \(N-1\)개의 복도로 이루어져 있다. 각 복도는 두 방을 연결하며, 일련의 복도를 따라 어느 방에서든 다른 어느 방으로도 걸어갈 수 있다.
헛간의 모든 방에는 벽에 원형 시계가 걸려 있고, 시계 판에는 표준적인 정수 \(1 \ldots 12\)가 둘려 있다. 그러나 이 시계에는 바늘이 하나뿐이며, 이 바늘은 항상 시계 판의 정수 중 하나를 정확히 가리킨다(두 정수 사이를 가리키는 일은 없다).
소 베시는 헛간의 모든 시계가 정수 12를 가리키도록 맞추고 싶다. 그러나 베시는 다소 단순해서, 헛간을 돌아다니며 방에 들어갈 때마다 그 방 시계의 바늘을 한 칸 앞으로 옮긴다. 예를 들어 시계가 5를 가리키고 있었다면 이제 6을 가리키게 되고, 12를 가리키고 있었다면 이제 1을 가리키게 된다. 베시가 같은 방에 여러 번 들어가면, 들어갈 때마다 그 방의 시계를 앞으로 돌린다.
베시가 걷기 시작할 방으로서, 모든 시계가 12를 가리키도록 만드는 것이 가능한 방의 개수를 구하시오. 베시는 시작 방의 시계를 처음에는 돌리지 않지만, 그 방에 다시 들어올 때마다 시계를 돌린다는 점에 주의한다. 시계는 저절로 움직이지 않으며, 베시가 그 방에 들어갈 때만 앞으로 간다. 또한 베시가 복도에 들어서면 반드시 반대쪽 끝으로 나가야 한다(복도를 일부만 걷다가 되돌아 같은 방으로 돌아오는 것은 허용되지 않는다).
문제 제공: Brian Dean
배점
- 테스트 케이스 2-7은 \(N\le 100\)을 만족한다.
- 테스트 케이스 8-15는 추가 제약이 없다.
문제 제공: Brian Dean
입력의 첫째 줄에 \(N\)이 주어진다. 다음 줄에 각 방의 초기 시계 상태를 나타내는, \(1 \ldots 12\) 범위의 정수 \(N\)개가 주어진다. 다음 \(N-1\)개의 줄 각각에 복도가 연결하는 두 방의 번호를 나타내는, \(1 \ldots N\) 범위의 두 정수 \(a\)와 \(b\)가 주어진다.
베시가 모든 시계를 12를 가리키도록 맞추는 것이 가능한 시작 방의 개수를 출력한다.
clocktree.in · 출력을 쓸 파일 clocktree.out4
11 10 11 11
1 2
2 3
2 41In 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).
riseoj 작성
출처 올림피아드 > USACO > 2019-2020 > February > Silver