結果

問題 No.872 All Tree Path
ユーザー ikdikd
提出日時 2019-08-30 23:55:43
言語 Nim
(2.0.2)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 941 bytes
コンパイル時間 1,392 ms
コンパイル使用メモリ 65,024 KB
最終ジャッジ日時 2024-07-02 16:02:19
合計ジャッジ時間 2,125 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
/home/judge/data/code/Main.nim(32, 37) Error: type mismatch: got 'seq[int]' for 'map(split(readLine(stdin), {' ', '\t', '\v', '\r', '\n', '\f'}, -1), parseInt)' but expected 'tuple'

ソースコード

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