아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

위대한 달걀 찾기

시간 제한3초메모리 제한1024 MB

요약
N개 방으로 이뤄진 트리에서 Egg First Search로 달걀을 찾는 기대 시간을 최소로 하는 시작 방을 모두 구합니다.
난이도

어려움10점 중 8점

유형
트리, 분할 정복, DFS
정답자
아직 제출이 없습니다

문제

매년 부활절에 Bob의 할머니는 가족 저택에서 The Great Egg Hunt를 연다. 이 행사는 Bob이 태어나기 전부터 이어져 온 가족 전통이다. 할머니는 먼저 커다란 부활절 달걀 안을 사탕으로 채운다. 그다음 방 하나를 균일한 확률로 무작위로 골라 달걀을 숨긴다. 달걀을 가장 먼저 찾은 사람이 그 안의 사탕을 모두 가진다.

저택에는 NN개의 방과 N−1N-1개의 문이 있으며, 각 문은 방 두 개를 잇는다. 저택은 연결되어 있어서, 문을 따라 어떤 방에서든 다른 모든 방으로 갈 수 있다.

Bob은 노련한 달걀 찾기 선수이며, Egg First Search라고 부르는 방법을 만들었다.

  1. Bob이 아직 탐색하지 않은 방에 있으면, 그 방을 탐색한다. Bob은 노련하므로 달걀이 그 방에 있으면 반드시 찾는다.
  2. 그렇지 않으면, Bob은 가장 가까운 미탐색 방이 있는 방향에 있는 인접한 방 중 하나로 이동한다. 그런 방이 여럿이면 균일한 확률로 무작위로 하나를 고른다.

방을 탐색하는 데 1 단위 시간이 걸리고, 인접한 방으로 이동하는 데도 1 단위 시간이 걸린다.

Bob은 탐색을 어느 방에서 시작할지 아직 정하지 못했다. 저택의 지도가 주어졌을 때, Egg First Search로 달걀을 찾는 기대 시간을 최소로 하는 시작 방을 모두 구하시오.

입력

첫 줄에 방의 개수를 나타내는 정수 NN (1≤N≤2⋅1051 \leq N \leq 2 \cdot 10^5)이 주어진다. 이어지는 N−1N-1개의 줄에는 문으로 직접 연결된 방 한 쌍을 나타내는 공백으로 구분된 정수 uu와 vv (1≤u,v≤N1 \leq u,v \leq N, u≠vu \neq v)가 한 줄에 하나씩 주어진다. 저택이 연결되어 있다는 것은 보장된다.

출력

첫 줄에 최적의 시작 방의 개수 MM을 출력한다. 둘째 줄에는 최적의 시작 방 S1,…,SMS_1, \ldots, S_M (1≤S1<S2<…<SM≤N1 \leq S_1 < S_2 < \ldots < S_M \leq N)을 공백으로 구분하여 출력한다.

예제2

  1. 예제 1

    입력
    3
    1 2
    2 3
    
    예상 출력
    2
    1 3
    
  2. 예제 2

    입력
    5
    1 2
    1 3
    1 4
    1 5
    
    예상 출력
    4
    2 3 4 5