문제

입력 , 출력

solution

import sys
from collections import deque

input = sys.stdin.readline
n = int(input())
arr = [[] for i in range(n + 1)]
res = 0


def dfs(idx, cost):
    global res
    for i, c in arr[idx]:
        if visited[i] == 0:
            visited[i] = cost + c
            dfs(i, c + cost)


for i in range(n):
    cur = list(map(int, input().split()))
    i = 1
    while 1:
        if cur[i] == -1:
            break
        arr[cur[0]].append((cur[i], cur[i + 1]))
        i += 2
visited = [0 for i in range(n + 1)]
dfs(1, 0)
visited[1] = 0
res = 0
idx = 0
for i in range(2, n + 1):
    if res < visited[i]:
        res = visited[i]
        idx = i
visited = [0 for i in range(n + 1)]
dfs(idx, 0)
visited[idx] = 0
print(max(visited))

설명

1. 특정 노드를 선택해서 가장 먼 거리에 있는 노드(B)를 찾는다.
2. 찾은 노드(B) 에서 dfs로 가장 먼 거리에 있는 노드의 거리가 트리의 지름이된다.

해당 알고리즘의 증명
트리의 지름 증명

트리의 지름을 구하는 방법만 알면
dfs를 두번 돌리면 풀리는 간단한 문제