ABC361 Eの解法メモ【Ruby】

入水目指して過去挑戦して解けてないAtCoder Problems上でDifficultyが水色の問題を解いていく。

ABC361 E: Tree and Hamilton Path 2概要

辺に重みを持つ木に対して、辺をたどってすべての頂点を訪れるときに経由した辺の重みの合計の最小値を求める問題。

解法イメージ

入力例1をベースに考える。
入力例1の木は頂点1から頂点2,3,4のそれぞれに辺が伸びている構造をしている。
この木に対してすべての頂点を訪れるような経路の例を考えてみると、$ 1 \rightarrow 2 \rightarrow 1 \rightarrow 3 \rightarrow 1 \rightarrow 4 $のような経路がある。

上記の経路のように、頂点2,3,4のような辺を一つしか持たない"行き止まり"の頂点は始点と終点にならない限り、辺を往復することになる。
逆に1度のみ経由で済む辺を考えてみると、始点から終点までをつなぐパスは戻ってくる必要がないため1度のみの移動で済む。それ以外の辺については始点と終点をつなぐパスに戻ってくる必要があるので、往復の2回通る必要が出てくる。
よって、すべての頂点を訪れるような経路の辺の重みの合計は、すべての辺の重みの合計の2倍から始点と終点をつなぐパスの重みの合計を引いたものになる。
この最小値を求めるとよいので、始点から終点までの辺の重みの合計が最大になるようなパスをみつければよい。
つまり木の直径を求めればよいので、直径を求めるアルゴリズムを使えばよい。

実装例

def dfs(first, hash)
  last = 0
  length = 0
  set = { first => true }
  queue = [[first, 0]]
  while queue.length > 0
    a, len = queue.pop
    hash[a].each do |b, blen|
      next if set[b]
    
      set[b] = true
      queue << [b, len + blen]
      if length < len + blen
        last = b
        length = len + blen
      end
    end
  end
  return last, length
end

n = gets.to_i
hash = Hash.new { |hash, key| hash[key] = {} }
sum = 0
(n-1).times do
  a, b, l = gets.split.map(&:to_i)
  hash[a][b] = l
  hash[b][a] = l
  sum += l
end

si, _ = dfs(1, hash)
puts 2 * sum - dfs(si, hash)[1]