結果

問題 No.3113 The farthest point
コンテスト
ユーザー ts yi
提出日時 2025-04-20 19:50:48
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
WA  
実行時間 -
コード長 1,190 bytes
コンパイル時間 173 ms
コンパイル使用メモリ 12,288 KB
実行使用メモリ 79,744 KB
最終ジャッジ日時 2025-04-20 19:51:08
合計ジャッジ時間 19,780 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2 WA * 1
other AC * 29 WA * 4
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
input = sys.stdin.readline

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

    parent = [-1] * N
    order = []
    stack = [0]
    parent[0] = -2  # ルートの親を特別マーク
    while stack:
        u = stack.pop()
        order.append(u)
        for v, _ in adj[u]:
            if parent[v] == -1:
                parent[v] = u
                stack.append(v)

    down = [0] * N
    NEG_INF = float('-inf')
    ans = NEG_INF

    # 逆順に DP
    for u in reversed(order):
        best1 = NEG_INF
        best2 = NEG_INF
        for v, w in adj[u]:
            if parent[v] == u:
                dc = down[v] + w
                if dc >= best1:
                    best2 = best1
                    best1 = dc
                elif dc > best2:
                    best2 = dc

        if best1 != NEG_INF:
            down[u] = best1
            ans = max(ans, best1)
        if best2 != NEG_INF:
            ans = max(ans, best1 + best2)

    print(ans)

if __name__ == '__main__':
    main()
0