白駿1167号樹の直径

9192 ワード
白駿 コセット パイ アルゴリズム#アルゴリズム# テキストリンク

白駿1167号樹の直径


問題のショートカット

コード#コード#

import sys

answer = 0
N = int(sys.stdin.readline())
tree = {i : [] for i in range(1, N+1)}
check = [-1]*(N+1)

for i in range(N):
  li = list(map(int, sys.stdin.readline().split()))
  root = li[0]
  li.pop()
  while len(li) > 1:
    dist = li.pop()
    node = li.pop() 
    tree[root].append((node, dist))


def findMaxIndex(node, check):
  for destination, dist in tree[node]:
    if check[destination] == -1:
      check[destination] = check[node] + dist  
      findMaxIndex(destination, check)

def dfs(node, r, visited):
  global answer
  for destination, dist in tree[node]:
    if destination not in visited:
      visited.add(node)
      dfs(destination, r+dist, visited)
      visited.remove(node)
    else:
      answer = max(answer, r)
    

findMaxIndex(1, check)
dist = 0
startNode = 1 
for i in range(1, N+1):
  if dist < check[i]:
    dist = check[i]
    startNode = i


dfs(startNode, 0, set())

print(answer)

🔧 トラブルシューティング


この問題は木が与えられ,各木に接続された幹線の重みがあることである.
ここでは,あるノードから別のノード(通過可能)への最大重み付け和を求める問題である.
この問題はDFSナビゲーションによって最初に解決しようとした.与えられたツリーのすべてのノードから、最大値の重み付け和をそれぞれ求め、最大値を返します.でも….ツリーのノード入力(2≦V≦100000)が大きいため,この方法は時間がかかりすぎる.
タイムアウトの問題を解決するには、最大値が発生する可能性のあるノードを事前に検索し、そのノードのみをナビゲートします.ツリー内のノードは接続されており、1つのノードから別のノードへの重みの和を求めることで最大値のノードが得られます.
👉 ここでは,1つのノードで得られる最大値だけを用いるべきではないか.このような疑問が発生する可能性がありますが、ノードの親ノードが存在する場合、この値は最終的な答えにはなりません.
したがって、findMaxIndexを使用して、dfsナビゲーションを行うノードを見つけて、ナビゲーションを行うことができます.

👍 ヘルプの反例リスト

4
1 2 5 3 9 -1
2 1 5 -1
3 1 9 4 8 -1
4 3 8 -1

답 : 22

6
1 2 3 -1
2 1 3 5 3 3 5 -1
3 2 5 4 7 -1
4 3 7 -1
5 2 3 6 5 -1
6 5 5 -1

답 : 20

4
1 2 7 3 2 -1
2 1 7 -1
3 1 2 4 3 -1
4 3 3 -1

답 : 12

5
1 2 7 3 2 5 10 -1
2 1 7 -1
3 1 2 4 3 -1
4 3 3 -1
5 1 10 -1

답 : 17
[白俊]1654号:網を切る
[TIL 16]javascript|==と==の違い