Baek Jun問題を解く-木の直径1967回

📜 理解问题

タイムアウトメモリは、回答を送信した人の回答率を制限します.
2秒128 MB 24229784741643.124%
質問する
ツリーは周期のない無方向図です.ツリーでは、どちらのノードを選択しても、2つのノードの間には常に1つのパスしか存在しません.ツリーから2つのノードを選択して両側に伸ばすと、最も長く伸びる場合があります.このとき、ツリー内のすべてのノードが、この2つのノードを直径の端点とする円内に入ります.

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

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

💡 問題の再定義

各ノードで最も長い2つのパスを見つけ、2つのパスとを見つけます.

▼▼▼計画作成

まず,無方向重み付け図を得るために,隣接テーブルを実現する.
次にbfsを行い,1番ノードは常にルートノードであるため,1番ノードからbfsを開始する.
bfsは、自分のサブノードの最大の重みを返します.この時点で最後のleafノードである場合は0を返します.bfsを実行すると、すべてのサブノードの重みが格納されます.
bfsを実行すると,サブノードの重みの値が得られると,最長2つの長さの和最大の値を求めることができる.サブノードが1つしかない場合があるため、この値は直径になります.

💻 計画の実行

import sys

sys.setrecursionlimit(100000)
adj_list = []
visited = []
node_diameter = []


def bfs(node):
    visited[node] = 1
    # leaf 일때
    if not adj_list[node]:
        return 0

    max_weight = 0
    for next_node in adj_list[node]:
        if not visited[next_node[0]]:
            node_weight = next_node[1] + bfs(next_node[0])
            node_diameter[node].append(node_weight)
            if max_weight < node_weight:
                max_weight = node_weight
    return max_weight


if __name__ == '__main__':
    N = int(sys.stdin.readline().strip())
    if N == 1:
        print(0)
    else:
        visited = [0 for _ in range(N + 1)]
        node_diameter = [[] for _ in range(N + 1)]
        adj_list = [[] for _ in range(N+1)]

        for _ in range(N - 1):
            node1, node2, weight = map(int, sys.stdin.readline().split())
            adj_list[node1].append([node2, weight])
            adj_list[node2].append([node1, weight])

        bfs(1)

        max_diameter = 0
        for weights in node_diameter:
            if len(weights) >= 2:
                first_max = weights.pop(weights.index(max(weights)))
                second_max = weights.pop(weights.index(max(weights)))
                diameter = first_max + second_max
            elif len(weights) == 1:
                diameter = weights.pop()
            else:
                diameter = 0
            if diameter > max_diameter:
                max_diameter = diameter
        print(max_diameter)

🤔 振り返る

最初にleafノードでbfsを行い,最長経路を探すアルゴリズムで実現したが,タイムアウト問題が発生し,考慮した結果,一度のbfsで実行できることが分かったので再実現した.複数回のbfsはタイムアウトの可能性のある問題です.