結果
問題 | No.1507 Road Blocked |
ユーザー |
|
提出日時 | 2021-05-14 22:33:09 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 321 ms / 2,000 ms |
コード長 | 589 bytes |
コンパイル時間 | 203 ms |
コンパイル使用メモリ | 82,560 KB |
実行使用メモリ | 177,024 KB |
最終ジャッジ日時 | 2024-10-02 02:22:08 |
合計ジャッジ時間 | 11,183 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 |
ソースコード
import sys sys.setrecursionlimit(2*10**5) n = int(input()) e = [[] for i in range(n)] for i in range(n-1): a,b = map(int,input().split()) a -= 1 b -= 1 e[a].append(b) e[b].append(a) mod = 998244353 count = [0]*n def dfs(x,p=-1): c = 1 for nex in e[x]: if nex == p: continue c += dfs(nex,x) count[x] = c return c dfs(0,-1) all = n*(n-1)//2*(n-1) ans = all for i in range(n): for j in e[i]: if count[j] > count[i]: continue ans -= count[j]*(n-count[j]) m = pow(all,mod-2,mod) print(ans*m%mod)