흑백 조경사
면접 대비시간 제한2초메모리 제한1024 MB
정점마다 흰색 또는 검은색이 칠해진 트리에서, 자손 중 다수 색이 각 자식 있는 정점의 색과 일치하도록 하는 루트를 모두 찾습니다.
문제
민아는 Even한 나무로 정원을 꾸미기로 유명한 조경사이다. 나무는 사이클이 없는 단순 연결 그래프이다. Even한 나무는 다음 조건을 만족하는 나무이다.
- 뿌리 정점이 하나 있다. 간선으로 연결된 두 정점은 부모-자식 관계를 가지며, 둘 중 뿌리 정점에 더 가까운 정점이 부모이다.
- 모든 정점은 흰색 또는 검은색으로 칠해져 있다.
- 자식이 없는 정점은 어떤 색이든 상관없다.
- 자식이 있는 정점은 모든 자손 정점의 색 중 더 많은 색으로 칠해져야 한다. 즉, 흰색 자손이 더 많으면 흰색, 검은색 자손이 더 많으면 검은색이어야 한다. 흰색 자손과 검은색 자손의 수가 같다면 어떤 색이든 상관없다. 이때, 서로 다른 두 정점 , 에 대해 에서 뿌리 정점으로 가는 단순 경로 위에 가 있다면 는 의 자손이다.
민아는 HCPC 대회장을 아름답게 꾸미려고 정점이 개인 나무 한 그루를 가져왔다. 그런데 대회장에 도착해 보니 어느 정점이 뿌리였는지 잊어버렸다. 뿌리를 어떤 정점으로 정하느냐에 따라 Even한 나무가 될 수도 있고 그렇지 않을 수도 있다. 뿌리로 정했을 때 나무가 Even해지는 정점을 모두 찾아라.
입력
첫째 줄에 정점의 개수 이 주어진다. ()
둘째 줄에 개의 정수 이 공백으로 구분되어 주어진다. 번 정점이 흰색이면 , 검은색이면 이다.
셋째 줄부터 줄에 걸쳐 나무의 각 간선이 잇는 두 정점의 번호 , 가 공백으로 구분되어 주어진다. (; )
출력
첫째 줄에 조건을 만족하는 정점의 수를 출력한다.
둘째 줄에 조건을 만족하는 모든 정점의 번호를 오름차순으로 공백으로 구분하여 출력한다.
조건을 만족하는 정점이 없다면 둘째 줄은 출력하지 않는다.