| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 5 초 | 1024 MB | 39 | 8 | 8 | 33.333% |
서울과학고의 기숙사는 $N$개의 방과 서로 다른 두 방을 연결하는 $N-1$개의 복도로 이루어진 트리 형태로 표현할 수 있다. 방들은 각각 1ドル$부터 $N$까지의 수 중 하나를 번호로 가지고 있다. 모든 복도는 양방향으로 이동할 수 있고, 복도를 이용해 모든 방 사이를 이동할 수 있다.
서울과학고에는 총 $N$명의 학생이 있으며, 각각 1ドル$부터 $N$까지의 수 중 하나를 번호로 가지고 있다. $i$번 학생은 기숙사의 $i$번 방에서 밤을 지낸다.
서울과학고에는 닌자부가 있다는 오랜 전설이 있다. 닌자부의 부원이 누구인지는 알려지지 않았으나, 적어도 한 명의 부원이 있다고 알려져 있다. 전설에 따르면, 이들은 밤마다 기숙사의 방 중 한 방에서 파티를 연다고 한다. 닌자부의 부원들은 다음과 같은 규칙으로 파티를 열 방을 정한다.
예를 들어, 서울과학고의 기숙사가 아래 그림과 같다고 하자. 닌자부에 소속된 학생들의 번호의 집합 $S=\{4,5,8\}$이라면, 파티가 열릴 조건을 위배하지 않는 방은 1ドル,ドル 2ドル,ドル 3ドル,ドル 4ドル,ドル 5ドル,ドル 8ドル$번 방이고, 이 중 번호가 가장 큰 8ドル$번 방에서 파티가 열리게 된다.
서울과학고의 학생들은 최근에 수학여행을 다녀왔다. 수학여행에서 묵은 숙소 역시 $N$개의 방과 서로 다른 두 방을 연결하는 $N-1$개의 복도로 이루어진 트리 형태로 표현할 수 있다.
열정이 많은 닌자부 부원들은 수학여행을 가서도 파티를 열었다. 이때 파티가 열리는 장소를 선택하는 방법은 이전과 같았다.
서울과학고 기숙사 사감인 지후는 서울과학고 기숙사와 수학여행 숙소에서 파티가 열린 방의 번호가 같다는 사실을 알게 되었다. 지후는 이 정보를 토대로 닌자부 부원들이 누구인지 알아내려고 한다. 닌자부 부원들의 번호의 집합으로 가능한 것의 개수를 구하여라.
첫째 줄에 학생의 수 $N$이 주어진다.
둘째 줄부터 $N$번째 줄까지 $i+1$번째 줄에는 두 정수 $A_i$와 $B_i$가 공백으로 구분되어 주어진다. 이는 서울과학고 기숙사의 $i$번째 복도가 방 $A_i$와 방 $B_i$를 연결한다는 뜻이다.
$N+1$번째 줄부터 2ドルN-1$번째 줄까지 $i+N$번째 줄에는 두 정수 $C_i$와 $D_i$가 공백으로 구분되어 주어진다. 이는 수학여행 숙소의 $i$번째 복도가 방 $C_i$와 방 $D_i$를 연결한다는 뜻이다.
닌자부에 소속된 부원들의 번호의 집합으로 가능한 것의 개수를 10ドル^9+7$로 나눈 나머지를 출력한다.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 13 | $N \le 10$ |
| 2 | 27 | $N \le 100$ |
| 3 | 28 | $N \le 5\ 000$ |
| 4 | 32 | 문제에 주어진 조건 외에 추가 제한 조건이 없다. |
4 2 1 2 3 2 4 4 1 4 2 4 3
11
6 1 2 1 3 1 4 4 5 4 6 1 2 2 3 3 4 4 5 5 6
63
School > 서울과학고등학교 > SciOI 2023 B-3번