結果
問題 | No.1418 Sum of Sum of Subtree Size |
ユーザー |
![]() |
提出日時 | 2023-02-02 01:14:28 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 853 bytes |
コンパイル時間 | 160 ms |
コンパイル使用メモリ | 82,176 KB |
実行使用メモリ | 98,044 KB |
最終ジャッジ日時 | 2024-07-01 18:17:43 |
合計ジャッジ時間 | 7,295 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 34 WA * 7 |
ソースコード
import sysreadline = sys.stdin.readlinedef non_rec_dfs(s):stack = []stack.append(s)par = [-1] * Nsz = [1] * Nglobal answhile stack:u = stack.pop()if u >= 0:stack.append(~u)for v in G[u]:if v == par[u]:continuepar[v] = ustack.append(v)else:u = ~usz[par[u]] += sz[u]for v in G[u]:if v == par[u]:continueans += sz[v] * (N - sz[v])ans += sz[u] * (N - sz[u])ans += NN = int(readline())G = [[] for i in range(N)]for i in range(N - 1):A, B = map(int, readline().split())A, B = A - 1, B - 1G[A].append(B)G[B].append(A)ans = 0non_rec_dfs(0)print(ans)