結果

問題 No.3113 The farthest point
コンテスト
ユーザー よいちなすの
提出日時 2025-04-18 21:35:38
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
AC  
実行時間 1,425 ms / 2,000 ms
コード長 819 bytes
コンパイル時間 175 ms
コンパイル使用メモリ 12,032 KB
実行使用メモリ 71,936 KB
最終ジャッジ日時 2025-04-18 21:36:07
合計ジャッジ時間 23,498 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 33
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
sys.setrecursionlimit(1 << 25)

N = int(input())
graph = [[] for _ in range(N)]

for _ in range(N - 1):
    u, v, w = map(int, input().split())
    u -= 1  # 0-indexed
    v -= 1
    graph[u].append((v, w))
    graph[v].append((u, w))

max_diameter = 0

def dfs(v, parent):
    global max_diameter
    longest = 0  # v から最長の子への距離
    second_longest = 0  # 2番目に長い子

    for child, weight in graph[v]:
        if child == parent:
            continue
        d = dfs(child, v) + weight
        if d > longest:
            second_longest = longest
            longest = d
        elif d > second_longest:
            second_longest = d

    # 直径候補の更新
    max_diameter = max(max_diameter, longest + second_longest)
    return longest

dfs(0, -1)
print(max_diameter)
0