용사의 여정
골드 V의견: 0
판타지 왕국에는 \(N\)개의 도시가 트리 형태로 연결되어 있다 (루트는 \(1\)번 도시). 두 용사가 각자의 출발 도시에서 수도(루트)를 향해 이동하면, 처음으로 공통으로 밟는 도시에서 만나게 된다. 이 도시가 바로 두 출발지의 최소 공통 조상(LCA)이다.
\(Q\)번의 쿼리가 주어진다. 각 쿼리는 두 도시 \(u\), \(v\)를 주고, \(\text{LCA}(u, v)\)를 구하여라.
- \(1 \le N \le 200\,000\)
- \(1 \le Q \le 200\,000\)
- \(1 \le u, v \le N\)
첫째 줄에 도시의 수 \(N\)과 쿼리의 수 \(Q\)가 공백으로 구분되어 주어진다.
다음 \(N-1\)개의 줄에 간선 \(u\) \(v\)가 주어진다.
다음 \(Q\)개의 줄에 쿼리 \(u\) \(v\)가 주어진다.
\(Q\)개의 줄에 걸쳐 각 쿼리의 \(\text{LCA}(u, v)\)를 출력한다.
6 3
1 2
1 3
1 4
2 5
2 6
3 5
5 6
3 4
1
2
1
노드 \(3\)과 \(5\)의 만남점: \(5\)는 \(2\)의 자식, \(3\)은 \(1\)의 자식이므로 \(3\)과 \(5\)의 LCA는 \(1\)이다. 노드 \(5\)와 \(6\)의 만남점: 둘 다 \(2\)의 자식이므로 LCA는 \(2\)이다. 노드 \(3\)과 \(4\)의 만남점: 둘 다 \(1\)의 자식이므로 LCA는 \(1\)이다.
5 3
1 2
2 3
3 4
4 5
3 5
1 5
2 4
3
1
2
체인 \(1\)-\(2\)-\(3\)-\(4\)-\(5\)에서 \(\text{LCA}(3,5)=3\), \(\text{LCA}(1,5)=1\), \(\text{LCA}(2,4)=2\).
막혔나요? 코인으로 단계별 힌트를 잠금 해제하세요 — 첫 힌트는 가벼운 방향 제시, 뒤로 갈수록 더 많이 알려 줍니다. 문제를 풀면 모든 힌트가 무료로 공개됩니다.
riseoj 작성
출처 Original
평가 및 의견
용사의 여정
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
용사의 여정