ツリーの直径

白駿1167号:木の直径

アイデア

ツリーで任意のノード(ルートノード)を捕まえ、dfsで最も遠いノードを検索します.そして,見つかったノードから最も遠いノードまでの距離が木の直径である.
どうしてこんなことになったの?最初は、ルートから離れた2つのノードを見つけて、2つを加えると正解だと思っていました.しかし、最初のノード(ルートノード)を通らずに直径が変わる場合もある.簡単な図でこのケースを理解してみましょう.

1枚の絵できれいに整理されている.
では、ルーティングノードはなく、ルーティングから最も遠いノードが通る場合もありませんか?このような状況も画像で知ることができます.

2番のパスは私たちが探しているパスで、3番のパスはルートノードで、ルートノードから最も遠い2つのノードが通らないパスです.不等式を作成し、少し計算することで、3番のパスが2番のパスより長くならないことがわかります.

コード#コード#

import sys
input = sys.stdin.readline

n = int(input())
tree = [[] for _ in range(n+1)]
dist = [0] * (n+1)
visited = [False] * (n+1)

for _ in range(n):
    input_list = list(map(int, input().split()))
    p = input_list[0]
    for i in range(1, len(input_list) - 1, 2):
        if i < 0:
            break
        tree[p].append((input_list[i], input_list[i+1]))

def dfs(n, v):
    for i in tree[n]:
        if not visited[i[0]]:
            visited[i[0]] = True
            d = dfs(i[0], v+i[1])
            dist[i[0]] = d
    return v

visited[1] = True
dfs(1, 0)

m = 0
idx = 0
for i in range(1, n+1):
    if dist[i] > m:
        m = dist[i]
        idx = i

visited = [False] * (n+1)
dist = [0] * (n+1)
visited[idx] = True
dfs(idx, 0)

print(max(dist))

おしゃべり

これらを直接考えている人の頭はどんなにいいですか.金魚です.