천사와 악마

트리로 구성된 세상에 천사와 악마들이 살고 있다.

각 천사들과 악마들이 어디 살고 있는지가 주어져 있다. 천사와 악마가 같이 사는 곳이 있을 수도 있다.

천사와 악마는 모두 한 곳에서 태어난 후 세상을 옮겨다니며 어디에서 살 지를 정했다. 천사는 출발지에서 최대 6 이하의 거리를 이동했고, 악마는 출발지에서 최소 3 이상의 거리를 이동했다. (단, 두 곳 사이의 거리는 반복 없이 이동했을 때 사이에 있는 간선의 개수로 정의한다.)

모든 천사와 악마가 태어난 곳으로 가능한 곳을 모두 표시하라.

사용법

• 천사가 있는 노드는 A, 악마가 있는 노드는 D가 적혀 있다.
• 한 노드에 천사와 악마가 모두 있을 수 있고, 이 경우에는 A/D가 적혀 있다.
• 각 노드를 클릭하여 출발지로 가능하다고 표시할 수 있다.

문제 형식

인터랙티브

출처

• KOI 2021 1차대회 고등부 1교시 16번
• KOI 2021 1차대회 중등부 1교시 17번