結果

問題 No.872 All Tree Path
ユーザー simansiman
提出日時 2021-08-02 18:19:12
言語 Ruby
(3.3.0)
結果
AC  
実行時間 1,234 ms / 3,000 ms
コード長 789 bytes
コンパイル時間 478 ms
コンパイル使用メモリ 11,204 KB
実行使用メモリ 302,412 KB
最終ジャッジ日時 2023-10-14 20:50:34
合計ジャッジ時間 13,619 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge13
外部呼び出し有り
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1,189 ms
59,736 KB
testcase_01 AC 1,201 ms
59,624 KB
testcase_02 AC 1,215 ms
59,736 KB
testcase_03 AC 1,222 ms
302,412 KB
testcase_04 AC 167 ms
15,400 KB
testcase_05 AC 1,234 ms
60,164 KB
testcase_06 AC 1,230 ms
60,172 KB
testcase_07 AC 1,224 ms
60,116 KB
testcase_08 AC 229 ms
20,188 KB
testcase_09 AC 227 ms
20,168 KB
testcase_10 AC 225 ms
19,916 KB
testcase_11 AC 232 ms
20,168 KB
testcase_12 AC 231 ms
20,060 KB
testcase_13 AC 155 ms
15,304 KB
testcase_14 AC 152 ms
15,216 KB
testcase_15 AC 153 ms
15,284 KB
testcase_16 AC 155 ms
15,420 KB
testcase_17 AC 154 ms
15,260 KB
testcase_18 AC 147 ms
15,256 KB
testcase_19 AC 155 ms
15,284 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
Syntax OK

ソースコード

diff # 

if !ENV['RUBY_THREAD_VM_STACK_SIZE']
  exec({'RUBY_THREAD_VM_STACK_SIZE'=>'1000000000'}, '/usr/bin/ruby', $0)
else
  N = gets.to_i
  E = Array.new(N + 1) { [] }
  V = Array.new(N + 1) { [] }

  (N - 1).times do
    u, v, w = gets.split.map(&:to_i)

    E[u] << [v, w]
    E[v] << [u, w]
  end

  def dfs1(u, cnt = 0, parent = -1)
    cnt = 0

    E[u].each do |v, w|
      next if v == parent

      v_cnt = dfs1(v, cnt, u)
      cnt += v_cnt
      V[u] << v_cnt
    end

    cnt + 1
  end

  $ans = 0

  def dfs2(u, v_cnt = 0, parent = -1)
    t_cnt = V[u].sum + v_cnt
    i = 0

    E[u].each do |v, w|
      next if v == parent

      cnt = V[u][i]
      $ans += 2 * w * (N - cnt) * cnt
      dfs2(v, t_cnt - cnt + 1, u)
      i += 1
    end
  end

  dfs1(1)
  dfs2(1)

  puts $ans
end
0