[파이썬] 백준 1761번: 정점들의 거리

백준 1761번: 정점들의 거리 1761번: 정점들의 거리 1761번 제출 맞힌 사람 숏코딩 재채점 결과 채점 현황 강의 질문 게시판 정점들의 거리 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 2 초 128 MB 10477 4190 2682 38.358% 문제 N(2 ≤ N ≤ 40,000)개의 정점으로 이루어진 트리가 주어지고 M(1 ≤ M ≤ 10,000)개의 두 노드 쌍을 입력받을 때 두 노드 사이의 거리를 출력하라. 입력 첫째 줄에 노드의 개수 N이 입력되고 다음 N-1개의 줄에 트리 상에 연결된 두 점과 거리를 입력받는다. 그 다음 줄에 M이 주어지고, 다음 M개의 줄에... www.acmicpc.net 접근 방법 (핵심 아이디어) Root에서부터 X까지의 거리를 f(X) 라고 했을때, A와 B사이의 거리는 f(A) + f(B) - 2f(lca(A,B)) 입니다. 위 정의에 따라 이 문제는 LCA를 구하는 문제입니다. 희소배열을 이용하여 logN의 시간복잡도로 L...

원문링크 : [파이썬] 백준 1761번: 정점들의 거리