結果
問題 | No.872 All Tree Path |
ユーザー |
![]() |
提出日時 | 2019-12-10 12:47:38 |
言語 | Ruby (3.4.1) |
結果 |
AC
|
実行時間 | 1,676 ms / 3,000 ms |
コード長 | 678 bytes |
コンパイル時間 | 185 ms |
コンパイル使用メモリ | 7,680 KB |
実行使用メモリ | 74,624 KB |
最終ジャッジ日時 | 2024-06-24 01:17:42 |
合計ジャッジ時間 | 16,246 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 18 |
コンパイルメッセージ
Syntax OK
ソースコード
Edge = Struct.new(:from, :to, :weight)N = gets.to_iG = Array.new(N + 1){ [] }T = Array.new(N + 1){ [] } # tree as root was 1C = Array.new(N + 1) # node count of subtree(1 ... N).each dou,v,w = gets.split.map(&:to_i)G[u] << Edge.new(u, v, w)G[v] << Edge.new(v, u, w)endused = Array.new(N + 1)stack = [1]used[1] = trueorder = []until stack.empty?u = stack.poporder << uG[u].each do |e|unless used[e.to]used[e.to] = truestack << e.toT[u] << eendendendorder.reverse_each{|u| C[u] = T[u].inject(1){|c, e| c + C[e.to] } }ans = T.flatten.inject(0){|s, e| s + e.weight * C[e.to] * (N - C[e.to]) * 2}puts ans