結果

問題 No.1507 Road Blocked
ユーザー ygd.
提出日時 2021-05-29 23:46:59
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 225 ms / 2,000 ms
コード長 1,188 bytes
コンパイル時間 160 ms
コンパイル使用メモリ 82,816 KB
実行使用メモリ 98,916 KB
最終ジャッジ日時 2024-11-08 10:54:21
合計ジャッジ時間 8,896 ms
ジャッジサーバーID
(参考情報)
judge4 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

import math
import sys
input = sys.stdin.buffer.readline
def main():
N = int(input()); MOD = 998244353
G = [[] for _ in range(N)]
branch =[]
for _ in range(N-1):
u,v = map(int,input().split())
u-=1;v-=1
G[u].append(v)
G[v].append(u)
branch.append((u,v))
root = 0
cnt = [0]*N
par = [-1]*N
stack = []
stack.append(~root)
stack.append(root)
while stack:
v = stack.pop()
if v >= 0:
for u in G[v]:
if u == par[v]: continue
par[u] = v
stack.append(~u)
stack.append(u)
else:
v = ~v
u = par[v]
cnt[v] += 1
if u == -1: continue
cnt[u] += cnt[v]
#print(cnt)
y = (N-1)*N*(N-1)//2; y%=MOD
x = y
for u,v in branch:
if v == par[u]:
u,v = v,u
#vu. par[v] = u
v_cnt = cnt[v]
u_cnt = N - v_cnt
x -= v_cnt*u_cnt%MOD
x %= MOD
#print(x,y)
g = math.gcd(x,y)
x //= g
y //= g
ans = x * pow(y,MOD-2,MOD)
print(ans%MOD)
if __name__ == '__main__':
main()
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0