[백준][Python] 11438 LCA2

[백준][Python] 11438 LCA2

LCA 기본형이다. LCA를 찾아 좌표를 반환하면 되는 문제

import sys sys.setrecursion(int(1e5)) input = sys.stdin.readline LOG = 21 # (1000000의 log2를 취한 값의 올림값)(2의 i승 단위의 부모값을 저장하기 위한 크기.) # 각 노드의 depth를 찾아 기록하기 위한 dfs def find_depth(cur_node, depth): check[cur_node] = True depth[cur_node] = depth for next_node in graph[x]: if not check[next_node]: parent[next_node][0] = cur_node find_depth(next_node, depth+1) # 공통조상 찾는 함수 def LCA(a,b): # b가 더 깊도록 설정 if depth[a] > depth[b]: a,b = b,a # 더 깊은 b에 대해 동일해질때까지 올린다. for i in range(LOG-1,-1,-1): if depth[b] - depth[a] >= (1<

from http://devlibrary00108.tistory.com/208 by ccl(A) rewrite - 2021-08-09 02:26:50