28472번 - Minimax Tree

문제

Minimax 알고리즘은 체스나 바둑, 틱택토와 같이 상대방과 번갈아가며 하는 게임에서 사용하는 알고리즘이다. 이 알고리즘에서 사용되는 Minimax 트리는 상대방의 최고의 수가 나에게 가장 최소의 영향을 끼치게 하기 위해 만든 게임트리이다. 즉, 한 사람을 기준으로 시작하는 사람이 모든 자식 노드 중 노드의 값이 큰 값을 선택하고 다른 사람은 모든 자식 노드 중 노드의 값이 가장 작은 값을 선택하여 최선의 전략을 찾아보는 방법이다.

Minimax Tree는 다음과 같이 구성된다.

• 트리에서 리프 노드의 값들은 모두 계산되어 있다.
• 게임에서 선 플레이어는 MAX player로 루트 노드부터 시작한다.
• 루트 노드부터 자식 노드로 내려갈 때마다 MAX player와 MIN player가 번갈아가며 바뀐다.
• 리프 노드가 아니면서 MAX player인 노드의 값은 자식 노드의 값들 중 최댓값으로 계산한다.
• 리프 노드가 아니면서 MIN player인 노드의 값은 자식 노드의 값들 중 최솟값으로 계산한다.

수민이는 친구와 게임을 하기로 하였다. 게임에서 이기면 받은 점수만큼 상품을 주기로 한다. 수민이는 최대한의 상품을 얻기 위해 인공지능 수업에서 배운 Minimax 트리를 그려 최적의 전략을 찾아 놓았다. 하지만 친구가 이를 눈치채고 트리에 있는 숫자들에 색칠을 하여 수민이를 방해하기 시작하였다. 그래도 일말의 양심은 남아있어 리프 노드는 건들지 않아서 값을 알 수 있다고 한다. Minimax 트리를 완성시켜 주기로 하자. 값을 구해야 할 노드들이 주어지면 그 노드의 값을 출력해 보자.

입력

첫째 줄에 트리 정점의 수 $N,ドル 루트의 번호 $R$가 공백으로 구분되어 주어진다. (2ドル \leq N \leq 10^5,ドル 1ドル \leq R \leq N$)

둘째 줄부터 $N$번째 줄까지 $N - 1$줄에 걸쳐 트리 간선의 양 끝 점 $u, v$가 공백으로 구분되어 주어진다. (1ドル \leq u,ドル $v \leq N,ドル $u \ne v$)

이어 리프 노드의 개수 $L$이 주어진다. (1ドル \leq L \leq N$이며 입력으로 주어진 트리의 리프 노드의 개수와 $L$은 항상 동일하다)

다음 $L$줄에 걸쳐, 리프 노드의 번호 $k_i$와 노드의 값 $t_i$가 공백으로 구분되어 주어진다. (1ドル \leq k_i \leq N,ドル 0ドル \leq t_i \leq 10^9,ドル 1ドル \leq i \leq L$)

이어 값을 구해야 할 노드의 개수 $Q$가 주어진다. (1ドル \leq Q \leq 10^5$)

다음 $Q$줄에 걸쳐, 값을 구해야 할 노드의 번호 $q_i$가 주어진다. (1ドル \leq q_i \leq N,ドル 1ドル \leq i \leq Q$)

출력

$Q$줄에 걸쳐 각 노드의 값을 출력한다.

제한

힌트