結果

問題 No.2598 Kadomatsu on Tree
ユーザー 👑 seekworser
提出日時 2024-01-03 04:51:50
言語 Nim
(2.2.0)
結果
AC  
実行時間 298 ms / 2,000 ms
コード長 621 bytes
コンパイル時間 3,736 ms
コンパイル使用メモリ 66,384 KB
実行使用メモリ 53,736 KB
最終ジャッジ日時 2024-09-27 18:23:52
合計ジャッジ時間 16,283 ms
ジャッジサーバーID
(参考情報)
judge2 / judge5
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 60
権限があれば一括ダウンロードができます
コンパイルメッセージ
/home/judge/data/code/Main.nim(24, 8) Warning: Number of spaces around '!=' is not consistent [Spacing]

ソースコード

diff #

import strutils,sequtils
var m=998244353
var n=stdin.readLine.parseint
var g=newSeqWith(n,newSeq[int](0))
for i in 0..<n-1:
 var u=stdin.readline.split.map(parseint).mapit(it-1)
 g[u[0]].add(u[1])
 g[u[1]].add(u[0])
var a=stdin.readLine.split.map(parseInt)
var ans=0
proc dfs(x,par:int):int=
 result=1
 var tl,tu=0
 for y in g[x]:
  if y==par: continue
  var sz=dfs(y,x)
  result+=sz
  if a[y]<a[x]:
   ans+=(tl*sz)mod m
   tl+=sz
  if a[x]<a[y]:
   ans+=(tu*sz)mod m
   tu+=sz
 if par!= -1:
  if a[par]<a[x]: ans+=(tl*(n-result))mod m
  if a[x]<a[par]: ans+=(tu*(n-result))mod m
 ans=ans mod m
discard dfs(0,-1)
echo ans
0