세계수 (Yggdrasil)

문제

인덱스국 종교사 : Day 3

인덱스국의 스택이 노예들의 폭동으로 무너진 이후, (검열됨)은 그 자리에 신성한 나무를 심었습니다. 나무는 열매가 열리는 N개의 가지와, 가지 사이를 연결하는 N − 1개의 줄기로 이루어져 있습니다. 신성한 나무는 한 그루뿐이기 때문에 모든 가지들은 연결되어 있습니다.

$i$번 가지에는 종류 $c_i$의 과실이 열리는데, 나무 관리자인 WGS는 이 중 몇 개를 몰래 따서 먹으려고 합니다. 하지만 국왕 (검열됨)이 매일 이 나무를 보러 오기 때문에 서리가 들통나지 않기 위해 다음의 규칙을 정했습니다 :

• 두 가지 s, e를 정해, s, e를 연결하는 경로에 있는 모든 열매들을 후보로 정한다. (s와 e도 후보에 포함된다)

• 이 때, 후보들 중 어떤 종류의 열매 개수가 전체 후보 수의 절반보다 크다면 그 종류의 열매를 하나 따먹는다.

WGS는 가장 맛있는 열매를 먹기 위해, Q쌍의 s, e를 정하고 각 선택을 분석하기로 했습니다.

이 문제를 잠시 고민하던 WGS는, 이내 부하인 당신에게 이 일을 떠넘겼습니다. WGS의 치졸함에 실망한 당신은 사표를 쓰기로 했지만, 그간의 정을 생각해 마지막으로 이 문제를 해결해주기로 했습니다.

구현 세부 사항

다음 함수를 구현하세요.

int[] getFruits(int C[], int U[], int V[], int S[], int E[])

• 이 함수는 처음 단 한 번 그레이더에 의해 호출됩니다.

• C는 크기 N의 배열로, 0 ≤ i ≤ N − 1에 대해 C[i] = $c_{i+1}$이며, i + 1번 가지에 열린 열매의 종류를 나타냅니다.

• U, V는 크기 N − 1의 배열로, 모든 0 ≤ i ≤ N − 2에 대해 가지 U[i]와 V[i]를 연결하는 줄기가 존재합니다.

• S, E는 크기 Q의 배열로, 각각 따먹을 열매의 후보를 정하는데 사용되는 s, e를 나타냅니다.

• 이 함수는 S[i], E[i]로 정의되는 질문에 대한 답; 따먹을 열매의 번호를 R[i]에 담고 있는, 크기 Q의 배열 R을 반환해야 합니다. 따먹을 수 있는 열매가 없다면 R[i] = −1입니다.

제한 조건

• 1 ≤ N ≤ 250,000

• 1 ≤ Q ≤ 250,000

• 1 ≤ C[i] ≤ N

• 1 ≤ U[i], V[i] ≤ N (0 ≤ i ≤ N − 2)

• 1 ≤ S[i], E[i] ≤ N (0 ≤ i ≤ Q − 1)

서브태스크

서브태스크	점수	제한 조건
1	2	N ≤ 1,000, Q ≤ 1,000
2	7	임의의 가지에 연결된 다른 가지는 2개 이하
3	6	추가 제한 조건 없음

예제 입출력

N = 7, Q = 4, C = [3, 1, 1, 2, 1, 1, 2], U = [1, 7, 2, 5, 5, 4], V = [3, 5, 3, 3, 6, 5], S = [1, 7, 3, 4], E = [4, 2, 3, 7]

그레이더는 다음 함수를 호출합니다.

getFruits([3, 1, 1, 2, 1, 1, 2], [1, 7, 2, 5, 5, 4], [3, 5, 3, 3, 6, 5], [1, 7, 3, 4], [4, 2, 3, 7]) = [−1, 1, 1, 2]

샘플 그레이더

Sample grader는 다음의 형식으로 입력을 받는다.

• line 1 : N Q
• line 2 : C[0] C[1] ··· C[N − 1]
• line 3 + i (0 ≤ i ≤ N − 2) : U[i] V[i]
• line N + 2 + i (0 ≤ i ≤ Q − 1) : S[i] E[i]