시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 (추가 시간 없음) 1024 MB 66 29 16 34.783%

문제

양의 정수를 원소로 갖는 유한집합 S에 대해, f(S)를 아래 조건을 만족하는 유한집합 중 가장 크기가 작은 집합으로 정의하며, 이러한 집합은 유일하게 존재한다.

  • S ⊆ f(S).
  • 임의의 양의 정수 x, y에 대해 x, y ∈ f(S), x ≠ y이면  x ⊕ y ∈ f(S)이다. (단, ⊕는 Bitwise-XOR)
  • 임의의 양의 정수 x에 대해 x ∈ f(S)이고 x < 21000이면 2x ∈ f(S)이다.
  • 임의의 양의 정수 x에 대해 2x ∈ f(S)이고 x < 21000이면 x ∈ f(S)이다.

점이 N개인 트리가 있다. 1 ≤ i ≤ N인 모든 i에 대해, i번 정점에는 양의 정수 Ai가 적혀있다. 이 때, 아래와 같은 Q개의 쿼리를 처리해야 한다.

쿼리 u, v에 대해, u번 정점에서 v번 정점에 이르는 최단경로에 포함되는 점들의 집합을 P라고 하자. 이 때 집합 f({ Ar | r ∈ P })의 원소 중 최솟값을 출력해야 한다.

입력

1번째 줄에 정점의 개수 N, 쿼리의 개수 Q가 공백으로 구분되어 주어진다.

2번째 줄에 각 정점에 적힌 양의 정수 A1, A2, ..., AN이 공백으로 구분되어 주어진다.

3번째 줄부터 N - 1개의 줄에 트리의 간선이 연결하는 두 정점의 번호 a, b가 공백으로 구분되어 주어진다.

N + 2번째 줄부터 Q개의 줄에 쿼리를 나타내는 두 정수 u, v가 공백으로 구분되어 주어진다.

출력

쿼리가 주어질 때마다 쿼리의 답을 한 줄에 하나씩, 총 Q개 줄에 걸쳐 출력한다.

제한

  • 1 ≤ N, Q ≤ 100,000
  • 0 < Ai < 230 (1 ≤ i ≤ N)
  • 모든 쿼리에서 1 ≤ u, v ≤ N

예제 입력 1

3 2
15 8 39
1 2
1 3
3 2
1 3

예제 출력 1

1
5

예제 입력 2

7 6
19 5 27 3 46 57 39
1 2
1 3
1 4
2 5
2 6
3 7
1 2
2 2
2 6
5 6
3 4
3 7

예제 출력 2

1
5
5
3
1
5

출처

Contest > IDTcup > 제 2회 IDTcup I번

  • 문제를 만든 사람: Diuven