만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

흑백 조경사

면접 대비

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

요약
정점마다 흰색 또는 검은색이 칠해진 트리에서, 자손 중 다수 색이 각 자식 있는 정점의 색과 일치하도록 하는 루트를 모두 찾습니다.
난이도

보통10점 중 6점

유형
트리, DFS, 동적 계획법
정답자
아직 제출이 없습니다

문제

민아는 Even한 나무로 정원을 꾸미기로 유명한 조경사이다. 나무는 사이클이 없는 단순 연결 그래프이다. Even한 나무는 다음 조건을 만족하는 나무이다.

  • 뿌리 정점이 하나 있다. 간선으로 연결된 두 정점은 부모-자식 관계를 가지며, 둘 중 뿌리 정점에 더 가까운 정점이 부모이다.
  • 모든 정점은 흰색 또는 검은색으로 칠해져 있다.
    • 자식이 없는 정점은 어떤 색이든 상관없다.
    • 자식이 있는 정점은 모든 자손 정점의 색 중 더 많은 색으로 칠해져야 한다. 즉, 흰색 자손이 더 많으면 흰색, 검은색 자손이 더 많으면 검은색이어야 한다. 흰색 자손과 검은색 자손의 수가 같다면 어떤 색이든 상관없다. 이때, 서로 다른 두 정점 aa, bb에 대해 aa에서 뿌리 정점으로 가는 단순 경로 위에 bb가 있다면 aa는 bb의 자손이다.

민아는 HCPC 대회장을 아름답게 꾸미려고 정점이 NN개인 나무 한 그루를 가져왔다. 그런데 대회장에 도착해 보니 어느 정점이 뿌리였는지 잊어버렸다. 뿌리를 어떤 정점으로 정하느냐에 따라 Even한 나무가 될 수도 있고 그렇지 않을 수도 있다. 뿌리로 정했을 때 나무가 Even해지는 정점을 모두 찾아라.

입력

첫째 줄에 정점의 개수 NN이 주어진다. (2≤N≤2000002 \le N \le 200000)

둘째 줄에 NN개의 정수 C1,C2,⋯ ,CNC_1, C_2, \cdots, C_N이 공백으로 구분되어 주어진다. ii번 정점이 흰색이면 Ci=0C_i=0, 검은색이면 Ci=1C_i=1이다.

셋째 줄부터 N−1N-1줄에 걸쳐 나무의 각 간선이 잇는 두 정점의 번호 uu, vv가 공백으로 구분되어 주어진다. (1≤u,v≤N1 \le u,v \le N; u≠vu \ne v)

출력

첫째 줄에 조건을 만족하는 정점의 수를 출력한다.

둘째 줄에 조건을 만족하는 모든 정점의 번호를 오름차순으로 공백으로 구분하여 출력한다.

조건을 만족하는 정점이 없다면 둘째 줄은 출력하지 않는다.

예제2

  1. 예제 1

    입력
    10
    0 0 0 1 1 0 1 1 0 0
    6 1
    6 3
    6 5
    6 7
    6 10
    5 2
    5 4
    7 8
    7 9
    
    예상 출력
    4
    1 3 6 10
    
  2. 예제 2

    입력
    8
    1 1 1 0 0 1 0 0
    3 8
    7 1
    6 4
    5 7
    2 4
    8 2
    4 5
    
    예상 출력
    0