結果

問題 No.3113 The farthest point
コンテスト
ユーザー ciffelia
提出日時 2025-04-20 16:43:13
言語 Python3
(3.15.0 + numpy 2.5.4 + scipy 1.18.1 + ACL)
コンパイル:
python3 -mpy_compile _filename_
実行:
python3 _filename_
結果
WJ  
(最新)
AC  
(最初)
実行時間 -
コード長 807 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
最終ジャッジ日時 2026-10-17 00:30:26
ジャッジサーバーID
（参考情報） 		judge2_0 / judge3_0
このコードへのチャレンジ
（要ログイン）

ソースコード

diff #
raw source code 

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