結果

問題 No.3113 The farthest point
ユーザー norioc
提出日時 2025-04-19 07:20:52
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,110 bytes
コンパイル時間 344 ms
コンパイル使用メモリ 82,040 KB
実行使用メモリ 128,504 KB
最終ジャッジ日時 2025-04-19 07:21:07
合計ジャッジ時間 13,773 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 20 WA * 13
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import defaultdict, deque


def tree_diameter_with_weight(n: int, adj: defaultdict) -> tuple[int, list]:
    def bfs(start):
        q = deque([start])
        dists = [-1] * n
        dists[start] = 0
        while q:
            v = q.popleft()
            for to, w in adj[v]:
                if dists[to] != -1: continue
                dists[to] = dists[v] + w
                q.append(to)

        return dists

    dists = bfs(0)
    _, ai = max((d, i) for i, d in enumerate(dists))
    dists = bfs(ai)
    d, bi = max((d, i) for i, d in enumerate(dists))
    path = [(bi, d)]  # (頂点番号, 距離)
    while path[-1][1] > 0:
        v, s = path[-1]
        for to, w in adj[v]:
            if dists[to] == s - w:
                path.append((to, s - w))
                break
        else:
            assert False

    return d, [v for v, _ in path]


N = int(input())
adj = defaultdict(list)
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))


d, _ = tree_diameter_with_weight(N, adj)
print(d)
0