Cijepise

Portal cijepise.zdravlje.hr은 크로아티아 공화국 주민이 COVID-19 백신 접종을 신청할 수 있게 한 기술 프로젝트다. 포털을 만드는 데 400만 쿠나를 조금 넘게 썼다. 주된 이유는 최고 수준의 알고리즘 전문가 팀이 이 개발에 참여했기 때문이다.

꼬마 Ante는 프로그래밍과 코코넛 아이스크림, 그리고 방역 수칙을 좋아한다. 당연히 그는 포털로 가까운 친구 $Q$명을 바로 접종 신청했다. 날짜도 정확히 기억한다. 3월 1일이었고, 그때 그는 지역 정보올림피아드를 준비하고 있었다. 그 사이 전국 대회가 열렸고, 크로아티아 로고 올림피아드도 열렸으며, Chelsea는 챔피언스리그 결승에 올랐다. 하지만 Ante의 친구 중 접종 호출을 받은 사람은 없었다.

Ante는 직접 나서기로 했다. 메시지를 보내고, 고객센터에 전화하고, 네트워크 트래픽을 가로채고, 컴파일과 디컴파일을 했다. 몇 시간 뒤 그는 포털이 돌아가는 원리를 알아냈고, 모든 사용자의 데이터에 접근하게 되었다. 이제 그에게는 진짜 알고리즘 전문가의 도움이 필요하다.

사용자는 내부적으로 트리 구조에 저장되어 있다. $N$명의 사용자는 각각 $(N - 1)$개의 간선을 가진 단순 연결 그래프의 $N$개 노드 중 하나에 대응한다. 노드에는 $1$부터 $N$까지의 자연수가 번호로 붙어 있고, 노드 $1$이 루트다. 접종 호출은 루트에 있는 사용자에게 초대장을 보내며 시작한다. 그 사용자는 시스템에서 삭제되고, 루트는 비게 된다. 이후 정확히 24시간 동안 복잡한 노드 이동 절차가 진행되며, 끝나면 다음으로 호출될 사용자가 루트에 나타난다.

노드 이동 절차는 먼저 루트와 나이가 가장 많은 자식을 서로 바꾼다. 이제 루트에는 어떤 사용자가 있고, 그 자식 중 하나가 빈 상태가 된다. 그다음 절차는 빈 자식과 그 자식의 가장 나이 많은 자식을 바꾸고, 이를 리프 중 하나가 빈 상태가 될 때까지 반복한다. 그러면 그 리프가 트리에서 삭제된다. 어느 단계에서든 한 노드가 가장 큰 나이를 가진 자식을 여럿 가지고 있다면, 알고리즘은 그중 가장 나이 많은 자식을 무작위로 고른다.

노드 이동 절차의 예시다(값은 사용자의 나이).

$Q$명의 친구 각각에 대해, Ante는 그 친구가 가장 적은 날수 안에 확실하게 호출되도록 나이를 바꿔야 하는 사용자 수의 최솟값을 알고 싶어 한다. Ante는 사용자의 나이를 $2 \cdot 10^9$ 이하의 음이 아닌 정수 중 아무 값으로나 바꿀 수 있다.

첫 줄에 문제에 나온 자연수 $N$이 주어진다.

둘째 줄에 $N$개의 정수 $x_i$($1 \le x_i \le 10^9$)가 주어진다. $x_i$는 노드 $i$에 있는 사용자의 나이다.

이어지는 $N - 1$개의 줄에는 자연수 $a_i$와 $b_i$($1 \le a_i, b_i \le N$)가 주어지며, 노드 $a_i$와 $b_i$ 사이에 간선이 있음을 뜻한다.

다음 줄에 문제에 나온 자연수 $Q$가 주어진다.

이어지는 $Q$개의 줄에는 자연수 $q_i$($1 \le q_i \le N$)가 주어지며, $i$번째 친구가 있는 노드 번호를 뜻한다.

$Q$명의 친구 각각에 대해, $i$번째 친구가 가장 적은 날수 안에 호출되도록 Ante가 나이를 바꿔야 하는 사용자 수의 최솟값을 한 줄에 하나씩 출력한다.