글 읽기 - 런타임 에러 지옥에서 구해주세요..

closet0426 4년 전 0

어느 부분을 고쳐야하는지...,,

조언 한말씀 부탁드립니다. .ㅠㅠ

from math import inf
from collections import deque
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

def find_lca(a,b):
    if depth[b] > depth[a]:
        a, b = b, a #d[a]가 항상 더 크다
    for i in range(len(parent[a])-1,-1,-1):
        if i >= len(parent[a]) : i = -1
        if (depth[a] - depth[b] >= (1<<i)): #DP 구조에 대해 다시 생각해보자
            #2^i 보다 차이가 큰 경우에는 depth가 큰 node의 parent로 업데이트한다
            #2^i 보다 두 노드의 depth 차이가 크다 --> 2^i 번째 node로 업데이트하면 차이를 줄 일 수 있다
            #2^i 보다 두 노드의 depth 차이가 작다 --> 2^i 번째 node로 업데이트하면 a,b 관계가 역전되므로 하지 않는다
            a = parent[a][i] #두 깊이의 차이가 다시 업데이트된다
    #최종족으로 d[a] == d[b]를 만족한다
    if a == b : return a
    for i in range(len(parent[a])-1,-1,-1):
        if i >= len(parent[a]): i = -1
        if parent[a][i] != parent[b][i]: #공통 조상을 갖지 않는다면
            a = parent[a][i] #a,b를 update한다
            b = parent[b][i]
    return parent[a][0] #최종 update된 값의 부모노드가 LCA로 확정된다

n = int(input().strip())
node = [[] for i in range(n+1)]
depth = [inf for i in range(n+1)]
parent = [[] for i in range(n+1)]

for i in range(n-1):
    a, b = map(int, input().strip().split())
    node[a].append(b)
    node[b].append(a)

Q = deque()
Q.append(1) #1번 노드가 root 노드가 된다
depth[1] = 0 #1번 노드의 depth를 1로 지정한다

while Q:
    cur = Q.pop()
    for link in node[cur]:
        if depth[link] == inf:
            depth[link] = depth[cur] + 1
            parent[link].append(cur) #parent[i][0] : parent에 해당한다
            Q.append(link)
            #현재 링크에 대해 ancestor들을 기록하자#
            num = 1
            while (2**num) <= depth[link]:
                num +=1
            for i in range(1, num):
                parent[link].append(parent[parent[link][-1]][i-1])

m = int(input().strip())
for i in range(m):
    a, b = map(int, input().strip().split())
    print(find_lca(a,b))

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

런타임 에러 지옥에서 구해주세요..

closet0426 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말