글 읽기 - 반례도 못찾겟구요,, 어디가 틀린지를 모르겠습니다..

qkrwnstns52 3년 전 0

어디가 문제죠?? ㅠㅠ 너무 답답합니다

import sys
sys.setrecursionlimit(int(1e5))

n = int(input())
parent = [0] * (n+1)
d = [0] * (n+1)
c = [0] * (n+1)
dist = [0] * (n+1)
graph = [[] for _ in range(n+1)]


for _ in range(n-1):
    a, b, z = map(int, input().split())
    graph[a].append((b, z))
    graph[b].append((a, z))

def dfs(x, depth):
    c[x] = True
    d[x] = depth
    for y in graph[x]:
        if c[y[0]]:
            continue
        parent[y[0]] = x
        dfs(y[0], depth+y[1])

def lca(a, b):
    while d[a] != d[b]:
        if d[a] > d[b]:
            a = parent[a]
        else:
            b = parent[b]
    while a != b:
        a = parent[a]
        b = parent[b]
    return a

dfs(1,0)
t = int(input())
for _ in range(t):
    s, e = map(int, input().split())
    common = lca(s, e)
    ans = d[s] + d[e] - d[common] * 2
    print(ans)

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

문제

문제

출처

ICPC

반례도 못찾겟구요,, 어디가 틀린지를 모르겠습니다..

qkrwnstns52 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말