시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 (추가 시간 없음) | 1024 MB | 96 | 44 | 27 | 38.028% |
양의 정수를 원소로 갖는 유한집합 S에 대해, 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개 줄에 걸쳐 출력한다.
3 2 15 8 39 1 2 1 3 3 2 1 3
1 5
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
1 5 5 3 1 5
Contest > BOJ User Contest > IDTcup > 제 2회 IDTcup I번