白駿-グラフ(#1967)


https://www.acmicpc.net/problem/1967

Code

import sys
sys.setrecursionlimit(10**9)

def dfs(node):
    for e,d in tree[node]:
        if dist[e] == 0:
            dist[e] = dist[node] + d
            dfs(e)

# make tree
n = int(input())
tree = {x:[] for x in range(1,n+1)}
for _ in range(n-1):
    inp = list(map(int, sys.stdin.readline().split()))
    tree[inp[0]].append([inp[1],inp[2]])
    tree[inp[1]].append([inp[0],inp[2]])

# find the farthest node from node 1
dist = [0]*(n+1)
if n > 1:
    dfs(1)
dist[1] = 0

farthest_node = 0
cnt = 0
for i in range(1,n+1):
    if dist[i] > cnt:
        cnt = dist[i]
        farthest_node = i

# find the farthest node from node 1
dist = [0]*(n+1)
if n > 1:
    dfs(farthest_node)
dist[farthest_node] = 0

result = 0
for i in range(1,n+1):
    if dist[i] > result:
        result = dist[i]
        farthest_node = i

print(result)   

リファレンス


#1167類似の問題
https://velog.io/@starteon/%EB%B0%B1%EC%A4%80-%EA%B7%B8%EB%9E%98%ED%94%84-1167