結果

問題 No.3113 The farthest point
コンテスト
ユーザー ciffelia
提出日時 2025-04-20 16:43:13
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
AC  
実行時間 1,111 ms / 2,000 ms
コード長 807 bytes
コンパイル時間 399 ms
コンパイル使用メモリ 12,288 KB
実行使用メモリ 86,636 KB
最終ジャッジ日時 2025-04-20 16:43:33
合計ジャッジ時間 18,363 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 33
権限があれば一括ダウンロードができます

ソースコード

diff # 

def solve():
    import sys
    sys.setrecursionlimit(1 << 25)
    N = int(sys.stdin.readline())
    from collections import defaultdict

    graph = defaultdict(list)
    for _ in range(N-1):
        u,v,w = map(int, sys.stdin.readline().split())
        graph[u-1].append((v-1, w))
        graph[v-1].append((u-1, w))

    ans = 0

    def dfs(u, parent):
        nonlocal ans
        max1, max2 = 0, 0  # 部分木の最大・2番目
        for v, w in graph[u]:
            if v == parent: continue
            res = dfs(v, u) + w
            res = max(res, 0)  # 負なら通らない
            if res > max1:
                max1, max2 = res, max1
            elif res > max2:
                max2 = res
        ans = max(ans, max1 + max2)
        return max1

    dfs(0, -1)
    print(ans)
solve()
0