(DFS & BFS) 백준 1167번 트리의 지름

import sys

input = sys.stdin.readline

V = int(input())

graph = [[] for i in range(V+1)] # dfs를 사용하기 위한 graph 생성

for _ in range(V):

    line = list(map(int, input().split())) # 입력을 리스트로 받는다.

    for i in range(1, len(line)//2): # 각 정점의 연결과 거리를 저장
        graph[line[0]].append([line[2*i-1], line[2*i]])


result = [0 for _ in range(V+1)]

def dfs(start, graph, result):
    for i, k in graph[start]:
        if result[i] == 0: # 아직 방문하지 않았으면
            result[i] = result[start] + k # 정점까지의 거리를 더한 값을 저장
            dfs(i, graph, result)


dfs(1, graph, result) # 1부터 시작
result[1] = 0 # 루트 노드가 정해져 있는게 아니라서 양 방향으로 입력을 받기 때문에 0으로 초기화

max_num = 0 # 최댓값 변수
index = 0 # 최장 경로

for i in range(len(result)): # 결과 값이 저장 된 result를 돌면서 max_num을 찾는다.
    if max_num < result[i]:
        max_num = result[i]
        index = i

answer = [0 for _ in range(V+1)] # 최장경로에서 다시 dfs를 통해 지름을 구한다.
dfs(index, graph, answer)
answer[index] = 0
print(max(answer))