\(N\)개의 정점으로 이루어진 트리가 주어진다.

각 정점 \(i\)에는 정수 \(A_i\)가 적혀 있다.

\(Q\)개의 질의가 주어진다.
각 질의는 세 정수 \(u, v, x\)로 이루어진다.

정점 \(u\)에서 정점 \(v\)로 가는 단순 경로 위에 있는 정점들 중 하나를 골라 그 정점에 적힌 값 \(A_i\)와 \(x\)의 XOR 값을 계산한다.

즉, 경로 위 정점 \(i\)에 대해 다음 값을 생각한다.

\(A_i \oplus x\)

각 질의마다 이 값의 최댓값을 출력하시오.

\(1 ≤ N ≤ 200\,000\)
\(1 ≤ Q ≤ 200\,000\)
\(0 ≤ A_i < 2^{30}\)
\(1 ≤ u, v ≤ N\)
\(0 ≤ x < 2^{30}\)
주어지는 그래프는 트리이다.

첫째 줄에 정점의 개수 \(N\)과 질의의 개수 \(Q\)가 주어진다.

둘째 줄에 \(N\)개의 정수 \(A_1, A_2, \dots, A_N\)이 공백으로 구분되어 주어진다.

셋째 줄부터 \(N-1\)개의 줄에 걸쳐 트리의 간선 정보 \(a\) \(b\)가 주어진다.

그 다음 줄부터 \(Q\)개의 줄에 걸쳐 질의 \(u\) \(v\) \(x\)가 주어진다.

각 질의마다 정점 \(u\)에서 정점 \(v\)로 가는 경로 위 정점 값들 중 \(x\)와 XOR 했을 때의 최댓값을 한 줄에 하나씩 출력한다.

anthony0506 작성

출처 anthony0506