RiseOJ – 서커스

설명

농부 존의 서커스단 소속 소 $$N$$ 마리( $1 \leq N \leq 10^5$ )가 다가오는 공연을 준비하고 있다. 공연은 모두 $1\ldots N$ 으로 번호가 매겨진 정점들을 가진 트리 위에서 이루어진다. 공연의 "시작 상태"는 수 $1 \leq K \leq N$ 과, 어떤 두 소도 같은 정점에 있지 않도록 소 $1\dots K$ 를 트리의 정점에 배정하는 방법으로 정의된다.

공연에서 소들은 임의로 많은 횟수의 "이동"을 한다. 한 번의 이동에서는 소 한 마리가 현재 정점에서 비어 있는 인접 정점으로 옮겨 간다. 어떤 이동의 나열을 통해 한 시작 상태에서 다른 시작 상태에 도달할 수 있으면, 두 시작 상태는 동치라고 한다.

각 $1 \leq K \leq N$ 에 대해, 시작 상태의 동치류의 개수, 즉 어느 두 개도 동치가 아니도록 고를 수 있는 시작 상태의 최대 개수를 소들이 구하도록 도와주자. 이 수들은 매우 클 수 있으므로, $$10^9 + 7$$ 로 나눈 나머지를 출력한다.

문제 제공: Dhruv Rohatgi

제약

배점

테스트 케이스 3-4는 $N\le 8$ 을 만족한다.
테스트 케이스 5-7은 $N\le 16$ 을 만족한다.
테스트 케이스 8-10은 $N\le 100$ 을 만족하며 트리는 "별(star)" 모양이다. 즉, 차수가 2보다 큰 정점이 많아야 하나이다.
테스트 케이스 11-15는 $N\le 100$ 을 만족한다.
테스트 케이스 16-20은 추가 제약이 없다.

문제 제공: Dhruv Rohatgi

입력 형식

첫째 줄에 $$N$$ 이 주어진다.

$2\le i\le N$ 번째 줄 각각에 트리에서 $$a_i$$ 와 $$b_i$$ 사이의 간선을 나타내는 두 정수 $$a_i$$ 와 $$b_i$$ 가 주어진다.

출력 형식

각 $1\le i\le N$ 에 대해, 출력의 $$i$$ 번째 줄에 $$K=i$$ 일 때의 답을 $$10^9+7$$ 로 나눈 나머지를 출력한다.

Standard input / output

This problem is judged over standard input/output. The original contest used named files — if you prefer the classic interface, tick “File I/O” on the submit form and read/write these files instead:

입력을 읽을 파일 circus.in · 출력을 쓸 파일 circus.out

예제 1

입력

출력

설명

For $$K=1$$ and $$K=2,$$ any two states can be transformed into one another.

Now consider $$K=3$$ , and let $$c_i$$ denote the location of cow $$i$$ . The state
$$(c_1,c_2,c_3)=(1,2,3)$$ is equivalent to the states $$(1,2,5)$$ and $$(1,3,2).$$
However, it is not equivalent to the state $$(2,1,3).$$

예제 2

입력

출력

문제 정보

riseoj 작성

출처 올림피아드 > USACO > 2019-2020 > US Open > Platinum

올림피아드 > USACO > 2019-2020 > US Open > Platinum

태그

JudgeUSACO

서커스

평가 및 의견

풀이 제출