시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 (추가 시간 없음) | 1024 MB (추가 메모리 없음) | 315 | 134 | 117 | 50.870% |
$10^{12}$ 개의 정점으로 이루어진 트리가 주어진다. 트리의 각 정점은 $1$번부터 $10^{12}$번까지 번호가 매겨져 있고 $1$번 정점은 루트이다.
이 트리는 다음과 같은 특수한 성질을 가지고 있다.
두 정점의 가장 가까운 공통 조상은, 두 정점을 모두 자손으로 가지면서 깊이가 가장 깊은 정점으로 정의한다.
두 정수 $a$와 $b$가 주어졌을 때, $a$번 정점과 $b$번 정점의 가장 가까운 공통 조상의 번호를 구해보자.
첫째 줄에 정수 $a$와 $b$가 공백으로 구분되어 주어진다. $(1\leq a,b\leq 10^{12})$
첫째 줄에 $a$번 정점과 $b$번 정점의 가장 가까운 공통 조상의 번호를 출력한다.
1 4
1
21 49
7
30 20
5
어떤 정점의 자손은 자기 자신을 포함한다.