[伯俊1967号]木の直径

百準1967題樹の直径

質問する

ツリーは周期のない無方向図です.ツリーでは、どちらのノードを選択しても、2つのノードの間には常に1つのパスしか存在しません.ツリーから2つのノードを選択して両側に伸ばすと、最も長く伸びる場合があります.このとき、ツリー内のすべてのノードが、この2つのノードを直径の端点とする円内に入ります.

この2つのノード間のパスの長さをツリーの直径と呼びます.正確には、ツリーのすべてのパスの中で最も長いパスです.
ルートツリーを重み付け幹線として入力すると、ツリーの直径を求めて出力するプログラムが作成されます.以下のツリーが指定されている場合、ツリーの直径は45です.

ツリーのノード番号は1～nです.

入力

ファイルの最初の行はノードの個数n(1≦n≦10000)である.2行目からn-1行に各幹線に関する情報があります.幹線に関する情報は3つの整数で構成されています.1番目の整数は、幹線接続の2つのノードの親ノードの番号を表し、2番目の整数は子ノードを表し、3番目の整数は幹線の重み値を表します.幹線に関する情報は、まず親ノード番号が小さいものを入力し、親ノード番号が同じ場合は、まず子ノード番号が小さいものを入力します.ルートノードの番号は常に1と仮定され、幹線の重みは100以下の正の整数です.

しゅつりょく

最初の行にツリーの直径を出力します.

import sys
sys.setrecursionlimit(100000)
from collections import defaultdict

# inputs
def max_diameter():

    n = int(sys.stdin.readline())
    graph = defaultdict(list)
    max_dia = [0]

    for _ in range(n-1):
        parent_node, child_node, weight = map(int, sys.stdin.readline().split())
        graph[parent_node].append((child_node, weight)) # 단방향


    def _dfs(curr, curr_weight):

        sub_length = [0]
        for next, next_weight in graph[curr]:
            sub_length.append(_dfs(next, next_weight))

        # update
        sub_length.sort(reverse=True)
        max_dia[0] = max(max_dia[0], sum(sub_length[:2])) 
        # 구한 길이 중 가장 긴 첫번째, 두번째 길이의 합과 현재 max 값 중 비교하여 max 값 갱신 
        return sub_length[0] + curr_weight # '가장 긴 거리 + 가중치' 반환

    _dfs(1, 0)
    return max_dia[0]

print(max_diameter())