結果
問題 |
No.1103 Directed Length Sum
|
ユーザー |
![]() |
提出日時 | 2023-01-02 17:44:53 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,651 ms / 3,000 ms |
コード長 | 849 bytes |
コンパイル時間 | 267 ms |
コンパイル使用メモリ | 82,304 KB |
実行使用メモリ | 260,840 KB |
最終ジャッジ日時 | 2024-11-27 01:10:04 |
合計ジャッジ時間 | 14,389 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 22 |
ソースコード
import sys readline = sys.stdin.readline def topsort(G): Q = [] count = [0] * N for u in range(len(G)): for v in G[u]: count[v] += 1 for u in range(len(G)): if count[u] == 0: Q.append(u) anslst = [] while Q: u = Q.pop() anslst.append(u) for v in G[u]: count[v] -= 1 if count[v] == 0: Q.append(v) anslst.reverse() return anslst N = int(readline()) mod = 10 ** 9 + 7 G = [[] for i in range(N)] for i in range(N - 1): A, B = map(int, readline().split()) A, B = A - 1, B - 1 G[A].append(B) size = [1] * N dp = [0] * N L = topsort(G) ans = 0 for n in L: for u in G[n]: dp[n] += dp[u] + size[u] dp[n] %= mod size[n] += size[u] ans += dp[n] ans %= mod print(ans)