結果

問題 No.3113 The farthest point
ユーザー tombo_
提出日時 2025-04-19 14:47:36
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 518 ms / 2,000 ms
コード長 1,556 bytes
コンパイル時間 555 ms
コンパイル使用メモリ 82,704 KB
実行使用メモリ 124,732 KB
最終ジャッジ日時 2025-04-19 14:47:49
合計ジャッジ時間 9,877 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 33
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import defaultdict
import sys
sys.setrecursionlimit(1 << 25)

class WeightedTree:
    def __init__(self, n):
        self.n = n
        self.graph = defaultdict(list)
        self.max_path_sum = float('-inf')  # グローバル最大値

    def add_edge(self, u, v, w):
        self.graph[u].append((v, w))
        self.graph[v].append((u, w))

    def dfs(self, node, parent):
        max1 = 0  # 部分木の中で最も重みが大きいパス
        max2 = 0  # 2番目に大きいパス（直径は2つの枝が合流してできることがある）

        for neighbor, weight in self.graph[node]:
            if neighbor == parent:
                continue
            res = self.dfs(neighbor, node) + weight
            if res > max1:
                max2 = max1
                max1 = res
            elif res > max2:
                max2 = res

        # 「このノードを中心としたパス」の最大値候補
        self.max_path_sum = max(self.max_path_sum, max1 + max2)

        # 親に返すのは、「このノードから伸びる最大の片道パス長」
        return max(max1, 0)  # 0未満なら無視

    def find_max_path_sum(self):
        self.dfs(1, -1)  # ノード番号が1から始まると仮定
        return self.max_path_sum

# ----------- 入力例と実行 -----------
if __name__ == "__main__":
    N = int(input())
    tree = WeightedTree(N)
    for _ in range(N - 1):
        u, v, w = map(int, input().split())
        tree.add_edge(u, v, w)
    print(tree.find_max_path_sum())
0