글 읽기 - 혼자 고민해보려고하는데 힘드네요.

jong_p 2년 전 0

반례 부탁해도 될까요..?

혼자 고민해보려고하는데 계속 틀리네요.. 반례도 여러개 찾아보고 스스로도 몇개 만들어서 돌려봤는데 잘 안되네요.

<코드 설명>

분할 정복을 통해 서브트리의 루트까지 만들 수 있는 가장 큰 길이를 이용합니다.

서브트리의 값을 이어 받아 서브트리까지 가는 경로를 더해 경로 길이를 연장합니다. 그리고 이를 tmp에 저장합니다. [0,좌측 경로 길이,우측 경로 길이]

좌측, 우측 경로를 합쳐서 전체 해가 될 수 있는지 확인합니다.

좌측,우측 경로 중 큰 것을 리턴합니다.

조금만 도와주시면 감사하겠습니다:)

global 같은 거에서 제가 모르는 에러라도 생겼는지 짐작은 해보는데 힘드네요..

from collections import defaultdict
import sys
input=sys.stdin.readline
#map(int,input().rstrip().split())

n=int(input())
graph=defaultdict(list)


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

res=0
def postorder(node):
    global res


    tmp=[0]
    for nxt,w in graph[node]:
        tmp.append(postorder(nxt))
        tmp[-1]+=w

    if res<sum(tmp):
        res=sum(tmp)

    return max(tmp)

postorder(1)
print(res)

jaehoo1 2년 전 0

안녕하세요

반례 드립니다

4
1 2 1
1 3 5
1 4 2
//정답 : 7
//출력 : 8

jong_p 2년 전 0

감사합니다!

jong_p 2년 전 1

@jaehoo1 단순히 바이너리 트리라고 생각해서 틀렸네요. 덕분에 해결했습니다.

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

문제

문제

출처

ICPC

혼자 고민해보려고하는데 힘드네요.

jong_p 2년 전 0

jaehoo1 2년 전 0

jong_p 2년 전 0

jong_p 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말