結果

問題 No.872 All Tree Path
ユーザー ikdikd
提出日時 2019-08-30 23:55:43
言語 Nim
(2.0.2)
結果
AC  
実行時間 406 ms / 3,000 ms
コード長 941 bytes
コンパイル時間 4,927 ms
コンパイル使用メモリ 69,188 KB
実行使用メモリ 50,916 KB
最終ジャッジ日時 2023-09-15 12:46:28
合計ジャッジ時間 9,872 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 381 ms
35,300 KB
testcase_01 AC 383 ms
35,264 KB
testcase_02 AC 406 ms
35,404 KB
testcase_03 AC 244 ms
50,916 KB
testcase_04 AC 2 ms
4,388 KB
testcase_05 AC 387 ms
35,240 KB
testcase_06 AC 387 ms
35,364 KB
testcase_07 AC 397 ms
35,372 KB
testcase_08 AC 27 ms
5,992 KB
testcase_09 AC 27 ms
6,000 KB
testcase_10 AC 27 ms
6,000 KB
testcase_11 AC 25 ms
5,924 KB
testcase_12 AC 25 ms
5,992 KB
testcase_13 AC 1 ms
4,384 KB
testcase_14 AC 1 ms
4,384 KB
testcase_15 AC 2 ms
4,384 KB
testcase_16 AC 2 ms
4,384 KB
testcase_17 AC 1 ms
4,384 KB
testcase_18 AC 2 ms
4,384 KB
testcase_19 AC 2 ms
4,384 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import strutils, sequtils

type Edge = tuple[to: int, d: int]
var 
  ans: int64 = 0
  dp: seq[int64]
  size: seq[int]

proc dfs(g: seq[seq[Edge]], i: int, p: int) =
  if dp[i] >= 0:
    return
  dp[i] = 0
  for e in g[i]:
    if e.to == p: continue
    dfs(g, e.to, i)
    size[i] += size[e.to]
    dp[i] += dp[e.to] + size[e.to] * e.d
  ans += dp[i]

proc sfd(g: seq[seq[Edge]], i: int, p: int, acc: int64) =
  for e in g[i]:
    if e.to == p: continue
    let nxt_acc = acc + (dp[i] - dp[e.to] - size[e.to] * e.d) + (size[0] - size[e.to]) * e.d
    sfd(g, e.to, i, nxt_acc)
    ans += nxt_acc
  
proc main() =
  let n = stdin.readLine.parseInt
  var g = newSeqWith(n, newSeq[Edge]())
  for i in 1..<n:
    var u, v, w: int
    (u, v, w) = stdin.readLine.split.map(parseInt)
    g[u - 1].add((v - 1, w))
    g[v - 1].add((u - 1, w))
  dp = newSeqWith(n, -1'i64)
  size = newSeqWith(n, 1)
  dfs(g, 0, -1)
  sfd(g, 0, -1, 0)
  echo ans
main()
0