結果

問題 No.872 All Tree Path
ユーザー siman
提出日時 2021-08-02 18:19:12
言語 Ruby
(3.4.1)
結果
RE  
(最新)
AC  
(最初)
実行時間 -
コード長 789 bytes
コンパイル時間 400 ms
コンパイル使用メモリ 7,424 KB
実行使用メモリ 12,416 KB
最終ジャッジ日時 2024-09-16 14:40:58
合計ジャッジ時間 3,749 ms
ジャッジサーバーID
(参考情報)
judge1 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample RE * 2
other RE * 18
権限があれば一括ダウンロードができます
コンパイルメッセージ
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
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0