結果

問題 No.3113 The farthest point
コンテスト
ユーザー issaimaru
提出日時 2025-04-19 22:37:33
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
AC  
実行時間 1,382 ms / 2,000 ms
コード長 697 bytes
コンパイル時間 224 ms
コンパイル使用メモリ 12,032 KB
実行使用メモリ 80,836 KB
最終ジャッジ日時 2025-04-19 22:37:59
合計ジャッジ時間 21,417 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 33
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
sys.setrecursionlimit(1 << 25)

N = int(input())
from collections import defaultdict

tree = defaultdict(list)

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

max_path = 0

def dfs(node, parent):
    global max_path
    best1, best2 = 0, 0  

    for neighbor, weight in tree[node]:
        if neighbor == parent:
            continue
        gain = dfs(neighbor, node) + weight
        gain = max(0, gain)  
        if gain > best1:
            best1, best2 = gain, best1
        elif gain > best2:
            best2 = gain

    max_path = max(max_path, best1 + best2)
    return best1

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