結果

問題 No.872 All Tree Path
ユーザー ikdikd
提出日時 2019-08-31 12:18:03
言語 Nim
(2.0.2)
結果
AC  
実行時間 356 ms / 3,000 ms
コード長 919 bytes
コンパイル時間 3,206 ms
コンパイル使用メモリ 69,176 KB
実行使用メモリ 52,804 KB
最終ジャッジ日時 2023-09-15 12:50:47
合計ジャッジ時間 7,160 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 349 ms
35,308 KB
testcase_01 AC 349 ms
35,220 KB
testcase_02 AC 354 ms
35,676 KB
testcase_03 AC 239 ms
52,804 KB
testcase_04 AC 2 ms
4,380 KB
testcase_05 AC 356 ms
35,400 KB
testcase_06 AC 350 ms
35,276 KB
testcase_07 AC 348 ms
35,308 KB
testcase_08 AC 25 ms
6,020 KB
testcase_09 AC 24 ms
6,184 KB
testcase_10 AC 25 ms
6,072 KB
testcase_11 AC 25 ms
6,000 KB
testcase_12 AC 25 ms
6,168 KB
testcase_13 AC 1 ms
4,380 KB
testcase_14 AC 2 ms
4,376 KB
testcase_15 AC 2 ms
4,376 KB
testcase_16 AC 1 ms
4,380 KB
testcase_17 AC 1 ms
4,376 KB
testcase_18 AC 2 ms
4,376 KB
testcase_19 AC 2 ms
4,376 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) =
  ans += acc
  for e in g[i]:
    if e.to == p: continue
    sfd(g, e.to, i, acc +
      (dp[i] - dp[e.to] - size[e.to] * e.d) +
      (size[0] - size[e.to]) * e.d)

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