25207번 - 바벨탑의 저주

바벨탑은 $N$개의 방이 $N$ - 1개의 통로로 연결된 이차원 건축물이다. 어떤 방들은 저주의 방으로, 접근하면 화를 입는다고 한다.

탑은 아래 그림과 같이 방과 통로가 각각 노드와 간선인 트리 그래프로 도식화할 수 있다. 각 노드에는 1 이상 $N$ 이하의 고유한 노드 번호가 있고, 번호가 $i$인 노드에는 중복될 수 있는 정수 $a_i$가 적혀있다. 루트 노드의 번호는 항상 1번이다. 한 부모 노드에게 자식 노드가 여럿이라면 노드 번호가 더 작은 자식이 왼쪽에 있다.

번호가 $i$인 노드를 루트 노드로 하며 그 노드의 부모 노드를 포함하지 않는 가장 큰 서브트리를 $T_i$라고 하자. $i$번 노드를 좌우로 뒤집으면 $T_i$에 속하는 모든 노드에 대해, 반대로 노드 번호가 더 큰 자식이 왼쪽에 있게 된다.

저주 노드란 좌우로 뒤집어도 전체 트리의 구조와 노드에 적힌 정수가 원래와 일치하는 노드이다. 위 그림에서 저주 노드들은 파란 테두리로 표시되어 있다. 당신의 임무는 모든 저주 노드의 번호를 알아내는 것이다.

첫째 줄에 노드의 수 $N$이 주어진다.

둘째 줄에 $a_1$부터 $a_N$까지의 $N$개의 정수가 공백으로 구분되어 주어진다.

다음 $N$ - 1 개의 줄에 걸쳐 두 정수 $i$, $j$가 공백으로 구분되어 주어진다. $i$번 노드가 $j$번 노드의 부모라는 뜻이다.

첫째 줄에 저주 노드의 수를 출력한다.

둘째 줄에 저주 노드들의 노드 번호를 작은 수부터 공백으로 구분하여 출력한다.

• 1 ≤ $N$ ≤ 500,000
• -10⁹ ≤ $a_i$ ≤ 10⁹