結果
問題 | No.1507 Road Blocked |
ユーザー |
|
提出日時 | 2022-06-18 12:47:33 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 368 ms / 2,000 ms |
コード長 | 780 bytes |
コンパイル時間 | 434 ms |
コンパイル使用メモリ | 82,432 KB |
実行使用メモリ | 200,832 KB |
最終ジャッジ日時 | 2024-10-10 01:15:05 |
合計ジャッジ時間 | 12,749 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 |
ソースコード
import syssys.setrecursionlimit(10**7)def invmod(a,mod):#mod逆元if a == 0:return 0if a == 1:return 1return (-invmod(mod % a, mod) * (mod // a)) % modN = int(input())lsg = [[] for i in range(N)]mod = 998244353for i in range(N-1):u,v = map(int,input().split())u -= 1v -= 1lsg[u].append(v)lsg[v].append(u)he = dict()chil = [1]*Nused = [False]*Ndef dfs(p,n):if used[n]:return chil[n]for j in lsg[n]:if j == p:continued = dfs(n,j)chil[n] += dhe[(j,n)] = dused[n] = Truereturn chil[n]dfs(-1,0)al = (N-1)*N*(N-1)//2for v in he.values():al -= v*(N-v)al %= moda = (N-1)*N*(N-1)//2a %= modav = invmod(a, mod)print((al*av)%mod)