문제

입력 , 출력

solution

import sys

sys.setrecursionlimit(10**5)
iuput = sys.stdin.readline


def dfs(a, b):
    global res
    sum = 0
    rcur = b
    sarr = []
    for i in arr[a]:
        cur = dfs(i[0], i[1])
        sarr.append(cur)
        rcur = max(b + cur, rcur)  # 밑에서 올라온것 중에 가장 높은값을 저장
    # 자식노드가 2개 이상일 경우도 있으니 반복문을 돌려 2개를 연결했을때 가장 큰 값을 지름으로 사용
    for i in range(len(sarr) - 1):
        for j in range(i + 1, len(sarr)):
            sum = max(sum, sarr[i] + sarr[j])
    res = max(res, sum, rcur) # sum을 다 합쳐도 일자로 한 것이 더 길 경우를 생각해서 rcur도 같이 넣어서 계산
	
    return rcur


n = int(input())
arr = [[] for i in range(n + 1)]
res = 0
for i in range(n - 1):
    a, b, c = map(int, input().split())
    arr[a].append([b, c])
dfs(1, 0)
print(res)

설명

키포인트

1. 이진트리가 아니다 자식 노드가 2개 이상일 경우도 생각해야함
2. 일자로 길이를 했을경우가 자식노드 두개를 연결했을 경우 보다 더 길 수도 있다.

DFS를 할 때 a -> b노드 의 가중치를 인자로 넣어준다.
다음 b의 자식노드를 돌아서 가장 긴 값을 받은 가중치 인자랑 더해서 return을 해준다.
만약 리프노드일 경우에는 받은 간선의 가중치 값만 return을 하게 된다.
그리고 자식노드가 2개 이상일 경우 두개를 이을 수 있는 모든 경우의 수를 반복문으로 확인하여
가장 높은값을 계산한다. 그리고 res에 저장된 값 보다 클경우 res값을 갱신해준다.
res의 값을 갱신해줄때 자식노드 2개를 이은것 보다 ( 가중치 b의 값 + 자식노드중 가장 긴 가중치 ) 도 같이 max함수에 넣어줘서
🔥🔥🔥🔥 [ res에 저장된값 , 자식노드 2개를 이은 값 , ( 가중치 인자 b의 값 + 자식노드중 가장 긴 가중치 ) ]
이 3개를 비교하여 res의 값을 갱신을 해준다.

후기

내가 이겼다.