최소 공통 조상 (LCA)

골드 III

난이도

시간 제한

256MB

메모리 제한

맞았습니다!!

제출 수

100.0%

정답률

레이팅

의견: 0

설명

정점이 $$N$$ 개이고 $$1$$ 번 정점을 루트로 하는 트리가 주어진다. 두 정점 $$u$$ , $$v$$ 의 최소 공통 조상(LCA)은 $$u$$ 와 $$v$$ 를 모두 자손으로 갖는 정점 중 루트에서 가장 멀리 떨어진(즉 깊이가 가장 깊은) 정점이다. 각 정점은 자기 자신의 조상으로도 본다.

$$M$$ 개의 질의가 주어진다. 각 질의마다 두 정점 $$u$$ , $$v$$ 의 최소 공통 조상을 출력하여라.

제약

$2 \le N \le 50\,000$ , $1 \le M \le 10\,000$ . $1 \le a, b, u, v \le N$ . 주어지는 간선들은 항상 하나의 트리를 이룬다.

입력 형식

첫째 줄에 정점의 개수 $$N$$ 이 주어진다. 다음 $$N-1$$ 개의 줄에 트리를 이루는 간선의 정보 $a\ b$ 가 주어진다 — 정점 $$a$$ 와 $$b$$ 를 잇는 간선이다 (간선은 방향이 없으며, 트리는 $$1$$ 번 정점을 루트로 한다).

그 다음 줄에 질의의 개수 $$M$$ 이 주어지고, 이어지는 $$M$$ 개의 줄에 질의 $u\ v$ 가 주어진다.

출력 형식

각 질의마다 한 줄에 두 정점 $$u$$ , $$v$$ 의 최소 공통 조상을 출력한다.

예제 1

입력

출력

설명

트리는 다음과 같다: $$1$$ 의 자식은 $$2$$ , $$3$$ ; $$2$$ 의 자식은 $$4$$ , $$5$$ ; $$3$$ 의 자식은 $$6$$ ; $$5$$ 의 자식은 $$7$$ , $$8$$ 이다.
$$4$$ 와 $$5$$ 의 LCA는 $$2$$ , $$7$$ 과 $$8$$ 의 LCA는 $$5$$ , $$4$$ 와 $$7$$ 의 LCA는 $$2$$ , $$6$$ 과 $$8$$ 의 LCA는 루트인 $$1$$ , $$3$$ 과 $$3$$ 의 LCA는 $$3$$ 자신, $$4$$ 와 $$6$$ 의 LCA는 $$1$$ 이다.